Торгівля#7482

Торгівля

1 секунда

128 мегабайтів

Дуже легка

Вздовж траси Алмати–Тараз розташовані $n$ міст, пронумерованих від $1$ до $n$ . З настанням зими $m$ невідомих торговців привезли з одного села в'язані шапки та почали продавати їх у цих населених пунктах.

Торговці дотримуються двох принципів:

Вони не торгують в одному місці більше одного дня.
Кожного дня вони збільшують ціну на шапку.

Більш формально кожний $i$ -ий торговець:

Починає торгівлю в населеному пункті $l_{i}$ l_i зі стартовою ціною $x_{i}$ x_i за одну шапку.
Кожного дня переходить у сусідній населений пункт: якщо напередодні він торгував у пункті $j$ , то сьогодні торгує у пункті $j + 1$ j+1.
Кожного дня збільшує ціну на $1$ : якщо вчора ціна становила $x$ , то сьогодні вона дорівнює $x + 1$ x+1.
Завершує торгівлю в населеному пункті $r_{i}$ r_i (при цьому в $r_{i}$ r_i він ще торгує).

Для кожного населеного пункту визначте максимальну ціну на одну шапку за всю історію торгівлі.

Вхідні дані

У першому рядку задано два цілих числа $n (1 \leq n \leq 3 \cdot 1 0^{5})$ n~(1 \le n \le 3 \cdot 10^5) та $m (1 \leq m \leq 3 \cdot 1 0^{5})$ m~(1 \le m \le 3 \cdot 10^5) — кількість населених пунктів та кількість торговців відповідно.

Далі слідують $m$ рядків, кожний з яких містить три цілих числа $l_{i}, r_{i} (1 \leq l_{i} \leq r_{i} \leq n)$ l_i, r_i~(1 \le l_i \le r_i \le n) та $x_{i} (1 \leq x_{i} \leq 1 0^{9})$ x_i~(1 \le x_i \le 10^9) — початковий і кінцевий населений пункт, а також стартова ціна на шапку для $i$ -го торговця.

Вихідні дані

Виведіть $n$ цілих чисел, де $i$ -е число позначає максимальну ціну на одну шапку за всю історію торгівлі в $i$ -му населеному пункті. Якщо в якомусь пункті торгівля не велася, виведіть $0$ .

Приклади

Приклад 1

Приклад 2