There are $n$ small villages close to the highway between Almaty and Taraz numbered from $1$ to $n$. At the beginning of the winter $m$ unknown traders began trading knitted hats in these villages. They have only two rules: never trade in one place more than once (one day) and increase the price on hats each day. More formally, each $i$-th trader: \begin{itemize} \item begins trading in village $l_i$ with starting price $x_i$. \item each day he moves to the next adjacent village, i.e. if he was trading in village $j$ yesterday, then today he is trading in village $j + 1$. \item each day he increases the price by $1$, so if yesterday's price was $x$, then today's price is $x + 1$. \item stops trading at village $r_i$ (after he traded his knitted hats in village $r_i$). \end{itemize} The problem is for each village to determine the maximal price that was there during the whole trading history. \InputFile Each line contains two integers $n\:(1 \le n \le 3 \cdot 10^5)$ and $m\:(1 \le m \le 3 \cdot 10^5)$ --- the number of villages and traders accordingly. Each of the next $m$ lines contains three integers: $l_i, r_i\:(1 \le l_i \le r_i \le n)$ and $x_i\:(1 \le x_i \le 10^9)$ --- the numbers of the first and the last village and starting price for the $i$-th trader. \OutputFile Output $n$ integer numbers separating them with spaces --- $i$-th number being the maximal price for the trading history of $i$-th village. If there was no trading in some village, output $0$ for it.