Стіна
Джан-Джі будує стіну з цеглин однакового розміру. Стіна складається з n стовпців цеглин, пронумерованих зліва направо від 0 до n - 1. Висотою стовпця називається кількість цеглин у ньому. У стовпців можуть бути різні висоти.
Джан-Джі будує стіну так. Спочатку в жодному зі стовпців немає цеглин. Далі Джан-Джі виконує k дій, кожна з яких може бути дією додавання або видалення цеглин. Будівництво вважається завершеним, коли виконані всі k дій. Перед кожною дією Джан-Джі обирає інтервал із послідовно розташованих стовпців і висоту h. Після цього він виконує одну з наступних дій:
дія додавання: Джан-Джі додає цеглини в стовпці з обраного інтервалу, висота яких менша ніж h, так, щоб вона стала рівною h. Зі стовпцями, висота яких не менша, ніж h, він нічого не робить;
дія видалення: Джан-Джі прибирає цеглини зі стовпців з обраного інтервалу, висота яких більша ніж h, так, щоб вона стала рівною h. Зі стовпцями, висота яких не більша, ніж h, він нічого не робить.
Потрібно визначити кінцеву форму стіни.
Приклад
Нехай є 10 колонок і 6 операцій зміни стіни. У всіх інтервалах у запитах межі включаються. Стан стіни після виконання кожної операції наведено нижче.
Оскільки спочатку висоти всіх стовпців дорівнюють нулю, після фази 0 кожна колонка від 1 до 8 буде містити 4 цеглини. Колонки 0 і 9 залишаються порожніми.
У фазі 1 цеглини видаляються в колонках з 4 до 8 поки кожна з них не буде містити 1 цеглину, колонка 9 залишається порожньою. Колонки з 0 до 3 знаходяться поза запитом, тому залишаються недоторканими.
У фазі 2 зміни не відбуваються в колонках з 3 по 6, оскільки вони не містять більше 5 цеглин.
Після дії 3 кількість цеглин у колонках 0, 4 і 5 збільшується до 3.
Є 5 цеглин у колонці 2 після дії 4.
Дія 5 видаляє всі цеглини в колонках 6 і 7.
Вхідні дані
Перша рядок містить два цілих числа n і k (1 ≤ n ≤ 2 * 10^6, 1 ≤ k ≤ 5 *10^5). n - кількість колонок у стіні, k - кількість операцій. Кожен з наступних k рядків має формат: op[i], left[i], right[i], height[i] (0 ≤ i ≤ k − 1). op[i] - тип операції i: 1 для додавання, 2 для видалення. Індекси стовпців, що беруть участь у i-ій операції, змінюються від left[i] до right[i] (включаючи кінці left[i] і right[i]). Відомо, що left[i] ≤ right[i]. height[i] - висота параметра i-ої операції.
Вихідні дані
Вивести n чисел, по одному в рядку. У рядку i вивести результуючу кількість цеглин у колонці i (0 ≤ i ≤ n − 1).