**Time limit:**1.00 s**Memory limit:**512 MB

Each operation consists of a range $[a,b]$ and a starting value $x$. This means that $A[a+k]$ becomes $\max(A[a+k],x+k)$ where $k=0,1,\dots,b-a$.

Your task is to print the final array after all operations.

**Input**

The first input line has two integers $n$ and $m$.

After this, there are $m$ lines that describe the operations. Each line has three values $a$, $b$ and $x$ according to the problem statement.

**Output**

Print the final array.

**Constraints**

- $1 \le n, m \le 10^5$

- $1 \le a \le b \le n$

- $1 \le x \le 10^9$

**Example**

Input:

`8 2`

1 6 1

5 7 100

Output:

`1 2 3 4 100 101 102 0`