Segment Tree - Multiple Update
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
liwith starting price
- 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
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:
ri (1 ≤
ri ≤ n) and
xi (1 ≤
109) - 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.
5 2 1 3 2 2 4 6
2 6 7 8 0
6 4 4 4 3 1 2 5 5 6 1 6 6 1
5 6 0 3 1 2