favorite We need a little bit of your help to keep things running, click on this banner to learn more

2013 IX Международная Жаутыковская Олимпиада Алматы, Казахстан, 16 января


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 integer number n (1n300000) and m (1m300000)  number of villages and traders accordingly.

Next m lines contains 3 numbers each: li, ri (1lirin) and xi (1xi109) - 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.

Time limit 1 second
Memory limit 122.17 MiB
Input example #1
5 2
1 3 2
2 4 6
Output example #1
2 6 7 8 0
Input example #2
6 4
4 4 3
1 2 5
5 6 1
6 6 1
Output example #2
5 6 0 3 1 2
Source 2013 IX Zhautykov Olympiad Almaty, Kazakhstan, January 16