Торговля

Вдоль трассы Алматы-Тараз есть $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$.

Примеры