Sequence Update Operations

You are given two sequences (a_1, a_2, \dots, a_n) and (b_1, b_2, \dots, b_n), where initially (b_i = 0) for all (1 \le i \le n).

Then, you need to perform (m) operations. In each operation, you are given three integers (l), (r), and (L). For each (k \in [l, r]), add (a_k) to (b_{L+k-l}). In other words, for every (k) in the interval ([l, r]), update:
[ b_{L + k - l} = b_{L + k - l} + a_k ]

After performing all operations, output the final sequence (b_1, b_2, \dots, b_n).

inputFormat

The first line contains two integers (n) and (m) separated by a space, representing the length of the sequences and the number of operations, respectively.

The second line contains (n) integers (a_1, a_2, \dots, a_n), separated by spaces.

Each of the next (m) lines contains three integers (l), (r), and (L) separated by spaces representing one operation.

outputFormat

Output the updated sequence (b_1, b_2, \dots, b_n) in one line, with each number separated by a space.

sample

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

2 3 5 7 3