Trading

There are $N$ villages beside the highway between Almaty and Taraz, numbered 1 to $N$. When winter began, $M$ traders started selling knitted hats in these villages. Every trader keeps two rules: he trades in one village for a single day, and he raises his price every day.

Trader $i$ behaves like this.

1. He starts trading in village $L_i$ at price $X_i$.
2. Every day he moves to the next village. If he traded in village $j$ yesterday, he trades in village $j+1$ today.
3. Every day he raises the price by 1. If yesterday's price was $x$, today's price is $x+1$.
4. He stops once he has sold his hats in village $R_i$.

For each village, find the highest price that was ever asked there.

The first line contains the number of villages $N$ and the number of traders $M$ ($1 \le N \le 300000$, $1 \le M \le 300000$).

Each of the next $M$ lines contains three integers $L_i$, $R_i$, $X_i$ ($1 \le L_i \le R_i \le N$, $1 \le X_i \le 10^9$): the first village, the last village, and the starting price of trader $i$, in that order.

Print $N$ integers on one line, separated by single spaces. The $i$-th number is the highest price ever asked in village $i$. Print 0 for a village where nobody traded.