You are given an array of ~n~ integers.

Then ~q~ queries follow. Each query contains three integers ~l, r, x~ and means to add ~x~ to every element from ~l~ to ~r~, inclusive.

After processing all queries, print the final array.

Input

The first line contains two integers ~n~ and ~q~, the length of the array and the number of queries.

The second line contains ~n~ integers: ~a_1, a_2, \ldots, a_n~.

Each of the next ~q~ lines contains three integers ~l, r, x~, meaning add ~x~ to every element ~a_l, a_{l + 1}, \ldots, a_r~.

Output

Print ~n~ space-separated integers: the final contents of the array after all ~q~ queries are applied.

Constraints

• ~1 \le n \le 2 \cdot 10^5~
• ~0 \le q \le 2 \cdot 10^5~
• ~1 \le l \le r \le n~
• ~-10^9 \le a_i \le 10^9~
• ~-10^9 \le x \le 10^9~

Example 1

Input

5 3
1 2 3 4 5
1 3 2
2 5 -1
4 4 7

Output

3 3 4 10 4

Explanation

After the three updates, the array becomes ~[3, 3, 4, 10, 4]~.

Example 2

Input

6 4
0 0 0 0 0 0
1 6 5
2 4 -3
3 3 10
6 6 -2

Output

5 2 12 2 5 3

Example 3

Input

4 0
8 -3 14 1

Output

8 -3 14 1