Стена
Джан-Джи строит стену из кирпичей одинакового размера. Стена состоит из 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).