Range Additions

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

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

3 3 4 10 4

Explanation

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

Example 2

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

5 2 12 2 5 3

Example 3

4 0
8 -3 14 1

8 -3 14 1