Впечатлившись фильмом «Пираты Корсарского моря 8», Поликарп решил найти клад, который по легенде закопан на одном из пляжей Берляндии. Следуя советам главного героя фильма, Поликарп быстро нашел и раскопал сундук с кладом.
К его разочарованию, на сундуке висел огромный замок, состоящий из n вращающихся дисков. На каждом из дисков записаны все целые числа от - 1013 до 1013. Также на каждом диске есть ровно одна важная позиция, в которой находится ровно одно число. Каждый из дисков можно прокручивать в любую сторону, чтобы изменять числа, стоящие в важных позициях.
Чтобы открыть замок, нужно прокрутить некоторые диски таким образом, чтобы выполнялись m условий. Условие i гласит, что сумма чисел, записанных на важных позициях дисков с номерами от li до ri включительно, должна равняться числу si.
Помогите Поликрапу! Выведите расположение дисков замка, при котором его можно открыть, либо сообщите, что замок открыть невозможно.
В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 3·105) — количество дисков на замке и количество необходимых для его открытия условий.
В каждой из следующих m строк следуют по три целых числа li, ri и si (1 ≤ li ≤ ri ≤ n, - 3·107 ≤ si ≤ 3·107) — описание очередного условия. Сначала следует номер самого левого диска, затем номер самого правого диска, а после этого требуемая сумма чисел на важных позициях дисков с номерами от li до ri включительно.
Если невозможно открыть замок, выведите в первую строку «NO» (без кавычек).
В противном случае, выведите в первую строку «YES» (без кавычек). Во вторую строку выведите n чисел, которые должны стоять на важных позициях дисков для открытия замка (то есть все m условий из входных данных должны выполняться для выведенного расположения дисков). Если ответов несколько, разрешается вывести любой из них.
5 4
1 2 5
1 3 8
2 5 11
4 5 3
YES
0 5 3 -8 11
5 4
2 3 5
1 3 8
2 5 11
4 5 3
NO
В первом примере суммы на соответствующих отрезках действительно равны заданным: a1 + a2 = 0 + 5 = 5 = s1, a1 + a2 + a3 = 8 = s2, a2 + a3 + a4 + a5 = 11 = s3 и a4 + a5 = 3 = s4.
Во втором примере можно доказать, что замок открыть невозможно. Для этого рассмотрим сумму на отрезке [2, 5]: с одной стороны a2 + a3 + a4 + a5 = (a2 + a3) + (a4 + a5) = s1 + s4 = 5 + 3 = 8, с другой стороны a2 + a3 + a4 + a5 = (a2 + a3 + a4 + a5) = s3 = 11.
