Difference Arrays

Problem Background

After learning prefix sums, Little J wants to unlock some new skills with the prefix-sum technique.

Now he wants to apply a series of range additions to an integer sequence and obtain the adjusted sequence.

Problem Description

For example, for the 5-element sequence 9 1 2 5 3, add 2 to every number in the interval [2, 4], then add 5 to every number in the interval [1, 4], then subtract 2 from every number in the interval [4, 5]; the resulting sequence is 14 8 9 10 1.

How should such code be written?

Input Format

The first line contains two positive integers $n(1\le n \le 10^6),m(1\le m \le 10^6)$.

The second line contains $n$ consecutive integers.

The following $m$ lines each contain three integers $x\,y\,z(0 \lt x \le y\le n, -10^6 \le z \le 10^6)$, meaning that $z$ is added to every number in the interval $[x,y]$.

Output Format

Print one line with the $n$ integers of the adjusted sequence.

Sample Input

5 3
9 1 2 5 3
2 4 2
1 4 5
4 5 -2

Sample Output

14 8 9 10 1