You are given an array \(A\) with \(N\) integers. Please apply the following \(Q\) operations:

Increment each item in the subarray of the range \([L, R]\) by a value of \(K\).

You will be required to output the final array once the \(Q\) operations have all been applied to the array.

Input Specification

The first line of the input will contain two integers \(N\) and \(Q\) \((1 \le N, Q \le 10^5)\), indicating the number of items and the number of operations.

The next line of the input will contain \(N\) integers \(A_i\) ranging from \(0\) to \(10^9\) inclusive, denoting the array \(A\).

The next \(Q\) lines will each contain three integers \(L\), \(R\), and \(K\) \((1 \le L \le R \le N, |K| \le 10^3)\), indicating the \(1\)-indexed indices of the subarray and the value used to increment each item.

Output Specification

On a single line output \(N\) integers, denoting the final array \(A\).

Sample Input 1

5 2
2 1 0 1 3
1 3 1
4 4 3

Sample Output 1

3 2 1 4 3

Sample Explanation 1

After the first operation, the resulting array is 3 2 1 1 3.

After the second operation, the resulting array is 3 2 1 4 3.