Вдоль трассы Алматы-Тараз есть $n$ населенных пунктов, пронумерованных числами от $1$ до $n$. В начале зимы $m$ неизвестных торговцев привезли из неизвестного аула вязаные шапки и начали ими торговать в этих населенных пунктах. У этих торговцев есть два принципа: не торговать в одном месте более одного раза (один день) и с каждым днем увеличивать цену на шапку. Более формально каждый $i$-ый торговец: \begin{itemize} \item Начинает торговать в населенном пункте $l_i$ со стартовой ценой на одну шапку $\:x_i$ \item Каждый день переходит в соседний населенный пункт, то есть, если вчера он торговал в населенном пункте $j$, то сегодня торгует в населенном пункте $\:j + 1$ \item Каждый день увеличивает цену на $1$, то есть, если вчера цена на его шапки была $x$, то сегодня цена $\:x + 1$ \item Завершает торговать в населенном пункте $r_i$ (при этом в пункте $r_i$ торговля происходит). \end{itemize} Наша задача для каждого населенного пункта определить максимальную цену на одну шапку за всю историю. \InputFile В первой строке находятся два целых числа $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$-го торговца соответственно. \OutputFile Выведите $n$ целых чисел, где $i$-ое число равно максимальной цене на одну шапку за всю историю продаж $i$-ого населенного пункта. Если в каком-то населенном пункте никто не торговал шапками, то для этого населенного пункта выведите $0$.