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 li with starting price xi.
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 ri (after he traded his knitted hats in village ri).
The problem is for each village to determine the maximal price that was there during the whole trading history.
Each line contains two integers n(1≤n≤3⋅105) and m(1≤m≤3⋅105) — the number of villages and traders accordingly.
Each of the next m lines contains three integers: li,ri(1≤li≤ri≤n) and xi(1≤xi≤109) — the numbers of the first and the last village and starting price for the i-th trader.
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.