# 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≤n≤3⋅10_{5})$ and $m(1≤m≤3⋅10_{5})$ — the number of villages and traders accordingly.

Each of the next $m$ lines contains three integers: $l_{i},r_{i}(1≤l_{i}≤r_{i}≤n)$ and $x_{i}(1≤x_{i}≤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.