Торгівля

Вздовж траси Алмати-Тараз розташовано $n$ населених пунктів, пронумерованих від $1$ до $n$. На початку зими $m$ невідомих торговців привезли з невідомого аулу в'язані шапки і почали їх продавати в цих населених пунктах. Торговці дотримуються двох принципів: не торгувати в одному місці більше одного разу (один день) і з кожним днем підвищувати ціну на шапку.

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

• Починає торгувати в населеному пункті $l_i$ зі стартовою ціною на одну шапку $x_i$.

• Щодня переходить у сусідній населений пункт, тобто, якщо вчора він торгував у населеному пункті $j$, то сьогодні торгує в населеному пункті $j+1$.

• Щодня збільшує ціну на $1$, тобто, якщо вчора ціна на його шапки була $x$, то сьогодні ціна $x+1$.

• Завершує торгувати в населеному пункті $r_i$ (при цьому в пункті $r_i$ торгівля відбувається).

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

Вхідні дані

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

У кожному з наступних $m$ рядків містяться три цілі числа $l_i,r_i(1\le l_i\le r_i\le n)$ і $x_i(1\le x_i\le 10^9)$ — номери початкового і кінцевого населених пунктів та початкова ціна на шапку для $i$-го торговця відповідно.

Вихідні дані

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

Приклади