Range Add Final Array - Classic Problems | Repovive

CLS44. Range Add Final Array

2s256 MB

Given an array of $n$ zeros, apply $q$ inclusive range additions. After all updates, print the final array.

\begin{array}{l} n \quad q \\ l_1 \quad r_1 \quad x_1 \\ l_2 \quad r_2 \quad x_2 \\ \vdots \\ l_q \quad r_q \quad x_q \end{array}

a_1 \quad a_2 \quad \ldots \quad a_n

Input

Explanation

After the three updates, the five final values are 2 3 3 -2 1.

Output

2 3 3 -2 1

Input

1 2
1 1 7
1 1 -2

Explanation

The only position receives 7 and then -2, leaving 5.

Output

Input

Explanation

Combining the four updates gives final values 10 5 14 14 14 0.

Output

10 5 14 14 14 0

Given an array of $n$ zeros, apply $q$ inclusive range additions. After all updates, print the final array.

\begin{array}{l} n \quad q \\ l_1 \quad r_1 \quad x_1 \\ l_2 \quad r_2 \quad x_2 \\ \vdots \\ l_q \quad r_q \quad x_q \end{array}

a_1 \quad a_2 \quad \ldots \quad a_n