You are given an array A of n elements and q update operation.

In every update operation, you will be given three integers l, r, x which means that in every index from l to r of the array A you have to add x ;

Input

In the first line, you will be given n and q, the size of the array and the number of the update operation.

Output

print n space separated integers, the final array after performs all update operation.

don't forget to print the new line after printing the n_th element of the array.

Constraint

1 <= n, q <= 100000 ;

1 <= l <= r <= n, 1 <= x <= 10⁹ ;

note: Initially the value of all the elements of the array is 0.

Example

Input:

5 3

1 4 3

2 5 1

3 5 2

Output:

3 4 6 6 3

explanation:

initially the elemnts of the array are: 0 0 0 0 0

After performing the first update operation, the array will be : 3 3 3 3 0

After performing the second update operation, the array will be: 3 4 4 4 1

After performing the 3rd operation, the array will be: 3 4 6 6 3

So the final array will be : 3 4 6 6 3