Competitions

# 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.

• 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.

#### Input

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` (1`li``ri`n) and `xi` (1`xi``109`) - numbers of first and last village and starting price for 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.

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