- 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