# ADA University - March 7 - Segment Tree

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

- begins trading in village
`l`

with starting price_{i}`x`

._{i} - 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
`r`

(after he traded his knitted hats in village_{i}`r`

)._{i}

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** (**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 ^{9}**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.

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