11853번 - 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:

1. begins trading in village L_i with starting price X_i.
2. 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.
3. each day he increases the price by 1, so if yesterday's price was x, then today's price is x + 1.
4. 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.

입력

Each line contains two integer number N (1 ≤ N ≤ 300000) and M (1 ≤ M ≤ 300000) - number of villages and traders accordingly.

Next M lines contains 3 numbers each: L_i, R_i (1 ≤ L_i ≤ R_i ≤ N) and X_i (1 ≤ X_i ≤ 10⁹) - numbers of first and last village and starting price for 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.

제한

힌트