Trading

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:

• begins trading in village $l_i$ with starting price $x_i$.

• 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$.

• each day he increases the price by $1$, so if yesterday's price was $x$, then today's price is $x+1$.

• stops trading at village $r_i$ (after he traded his knitted hats in village $r_i$).

The problem is for each village to determine the maximal price that was there during the whole trading history.

Input

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.

Output

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.

Examples