Стіна

Вхідні дані

Перша строчка містить два цілих числа $n$ і k~(1 \le n \le 2 \cdot 10^6, 1 \le k \le 5 \cdot 10^5) — кількість стовпців у стіні та кількість операцій.

Кожна із наступних $k$ строчок містить чотири значення:

• op_i — тип операції: $1$ відповідає додаванню, $2$ — видаленню.

• Індекси стовпців у $i$-й операції змінюються від left_i до right_i включно. Гарантується, що left_i \le right_i.

• height_i — параметр висоти у даній операції.

Вихідні дані

Виведіть $n$ чисел, кожне у окремому рядку. У рядку $i$ повинно бути зазначено кінцеву кількість цеглин у стовпці i~(0 \le i \le n - 1).

Приклади

Нехай є $10$ стовпців і $6$ операцій зміни стіни. У всіх запитах границі інтервалів включаються. Стан стіни після виконання кожної операції показано нижче.

• Оскільки спочатку висоти всіх стовпців дорівнюють нулю, після фази $0$ кожний стовпець з $1$ по $8$ буде містити по $4$ цеглини. Стовпці $0$ та $9$ залишаються порожніми.

• У фазі $1$ цеглини видаляються у стовпцях з $4$ по $8$ так, щоб у кожному з них залишилося по $1$ цеглині. Стовпець $9$ залишається порожнім. Стовпці з $0$ по $3$ поза інтервалом запиту, тому вони не змінюються.

• У фазі $2$ зміни у стовпцях з $3$ по $6$ не відбуваються, оскільки їх висота не перевищує $5$.

• Після дії $3$ кількість цеглин у стовпцях $0,4$ і $5$ збільшується до $3$.

• Після дії $4$ у стовпці $2$ стає $5$ цеглин.

• Дія $5$ видаляє всі цеглини у стовпцях $6$ і $7$.