Изначально был дан массив \(a\), состоящий из \(n\) целых чисел. Позиции в нем пронумерованы от \(1\) до \(n\).
К массиву применили ровно \(q\) запросов. Для \(i\)-го запроса выбирался некоторый отрезок \((l_i, r_i)\) \((1 \le l_i \le r_i \le n)\), и значения элементов на позициях от \(l_i\) до \(r_i\) включительно заменялись на \(i\). Порядок запросов не может быть изменен, и все \(q\) запросов были применены. Также известно, что каждая позиция от \(1\) до \(n\) была покрыта хотя бы одним отрезком.
Мы бы могли вам предложить задачу о проверке того, что некоторый массив (состоящий из \(n\) целых чисел со значениями от \(1\) до \(q\)) мог быть получен приведенными выше запросами. Однако, мы решили, что данная задача будет слишком проста для вас.
Улучшение, которое мы к ней применили, заключается в следующем. Было выбрано множество позиций (возможно пустое) в данном массиве, и значения элементов на этих позициях были заменены на \(0\).
Ваша задача — проверить, что такой массив мог быть получен приведенными выше запросами. Также, если мог, то восстановить этот массив.
Если существует несколько возможных массивов, то выведите любой из них.
Выходные данные
Выведите «YES», если массив \(a\) может быть получен применением \(q\) запросов. Отрезки \((l_i, r_i)\) \((1 \le l_i \le r_i \le n)\) выбираются независимо друг от друга при каждом запросе. Каждая позиция от \(1\) до \(n\) должна быть покрыта хотя бы одним отрезком.
В противном случае выведите «NO».
Если некоторый массив мог быть получен, то выведите \(n\) целых чисел во второй строке — \(i\)-е число должно быть равно значению \(i\)-го элемента полученного массива и должно иметь значение от \(1\) до \(q\). Должно быть возможно получить данный массив применением ровно \(q\) запросов.
Если существует несколько возможных массивов, то выведите любой из них.
Примечание
В первом примере можно также заменить \(0\) значением \(1\), но не \(3\).
Во втором примере не важно, какие отрезки выбирались до запроса \(10\), при котором был запрос \((1, 3)\).
Третий пример демонстрирует тот факт, что порядок операций не может быть изменен, нельзя сначала присвоить элементы \((1, 3)\) значению \(6\), и только потом \((2, 2)\) значению \(5\). Отрезок для \(5\) должен быть применен до отрезка для \(6\).
В четвертом примере существует много корректных ответов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 0 2 3
|
YES
1 2 2 3
|
|
2
|
3 10
10 10 10
|
YES
10 10 10
|
|
3
|
5 6
6 5 6 2 2
|
NO
|
|
4
|
3 5
0 0 0
|
YES
5 4 2
|