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