A. Левко и восстановление массива
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Левко сильно любит массив a1, a2, ... , an, состоящий из целых чисел. Именно поэтому Левко много играет с массивом a, выполняя различные операции с ним. Каждая операция, которую выполняет Левко, имеет один из двух следующих типов:

  1. Увеличить все элементы от li до ri на di. Другими словами выполнить присвоения aj = aj + di для всех j, удовлетворяющих неравенству: li ≤ j ≤ ri.
  2. Найти максимум элементов от li до ri. То есть посчитать значение .

К большому сожалению, недавно Левко потерял свой массив. К счастью, у Левко остались записи всех операций, которые он выполнял с массивом a. Помогите Левко — по записям операций найдите хотя бы один подходящий массив. Результаты всех операций для найденного массива должны совпадать с результатами из записей. Левко точно помнит, что в его массиве все числа не превосходили 109 по модулю, поэтому он просит вас найти именно такой массив.

Входные данные

В первой строке записаны два целых числа n и m (1 ≤ n, m ≤ 5000) — размер массива и количество операций в записях Левко соответственно.

Следующие m строк описывают операции, i-ая строка описывает i-ую операцию. Первое число в i-ой строке — целое число ti (1 ≤ ti ≤ 2), которое обозначает тип операции. Если ti = 1, то далее следуют три целых числа li, ri и di (1 ≤ li ≤ ri ≤ n,  - 104 ≤ di ≤ 104) — описание операции первого типа. Если ti = 2, то далее следуют три целых числа li, ri и mi (1 ≤ li ≤ ri ≤ n,  - 5·107 ≤ mi ≤ 5·107) — описание операции второго типа.

Операции заданы в том порядке, в котором Левко выполнял их со своим массивом.

Выходные данные

В первой строке выведите «YES» (без кавычек), если решение существует, и «NO» (без кавычек) в противном случае.

Если решение все-таки существует, то во второй строке выведите n целых чисел a1, a2, ... , an (|ai| ≤ 109) — найденный массив.

Примеры
Входные данные
4 5
1 2 3 1
2 1 2 8
2 3 4 7
1 1 3 3
2 3 4 8
Выходные данные
YES
4 7 4 7
Входные данные
4 5
1 2 3 1
2 1 2 8
2 3 4 7
1 1 3 3
2 3 4 13
Выходные данные
NO