There is an array $A$ of $n$ numbers $A[1],A[2],\dots,A[n]$. Initially each array value is $0$, but the array will be modified using $m$ operations.

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