You are given an array ~a~ of length ~N~. There are ~Q~ updates of the form l r v, which means to add ~v~ to all elements in the subarray ~[l, r]~.

You would like to know the array after these updates.

Input Specification

The first line will contain two integers, ~N, Q~ ~(1 \le N, Q \le 10^5)~.

The second line will contain ~N~ integers, ~a_1, a_2, \ldots, a_N~ ~(0 \le a_i \le 10^9)~, the initial array.

The next ~Q~ lines will each contain an update of the form described above. It is guaranteed ~1 \le l \le r~ and ~1 \le v \le 10^9~.

Output Specification

Output the array after these updates on a single line.

Subtasks

Subtask [20%]

~N, Q \le 100~

Subtask [80%]

No further constraints.

Sample Input

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

Sample Output

4 6 16 11 3