You are given a sequence of nonnegative integers \(a_1, a_2, \ldots, a_N\) of length \(N\).

There are \(Q\) operations. The \(i\)-th operation is described by three positive integers \(L_i, R_i, b_i\) and adds \(b_i\) to every element in the range \([L_i, R_i]\).

After performing all operations, output the final sequence \(a\).

Input

The first line contains two integers \(N\) and \(Q\).

The second line contains \(N\) nonnegative integers \(a_1, a_2, \ldots, a_N\).

Each of the next \(Q\) lines contains three integers \(L_i, R_i, b_i\), describing one operation.

Constraints

• \(1 \le N, Q \le 2 \times 10^5\)
• \(0 \le a_i \le 10^4\)
• \(1 \le b_i \le 10^4\)
• \(1 \le L_i \le R_i \le N\)

Output

Output a single line containing \(N\) integers: the sequence \(a\) after applying all \(Q\) operations.

Scoring

There are two subtasks. Each subtask contains multiple test cases, and you earn the subtask's score only if you solve all of its tests.

• Subtask \(1\) (60 points): \(a_i = 0\) for all \(i\).
• Subtask \(2\) (40 points): no additional constraints.

Sample Input 1

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

Sample Output 1

2 3 7 6 4

Sample Input 2

4 2
2 0 4 8
1 3 1
3 4 1

Sample Output 2

3 1 6 9