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

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