Apply \(Q\) inclusive range additions to an array. Update indices are zero-based.

Input

The first line contains \(N\) and \(Q\). The second line contains \(N\) integers \(A_i\). Each update contains \(L,R,K\) and adds \(K\) to every index from \(L\) through \(R\).

The input satisfies:

• \(1 \le N \le 10^6\)
• \(1 \le Q \le 10^5\)
• \(0 \le L \le R < N\)
• \(0 \le A_i, K \le 1000\)

Output

Print the final array with elements separated by single spaces.

Example

Input

1 1
3
0 0 5

Output

8