#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

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.

Constraints

$1 \le n, q \le 2 \cdot 10^5$
$1 \le l \le r \le n$
$-10^9 \le x \le 10^9$

Input

\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}

Output

a_1 \quad a_2 \quad \ldots \quad a_n

Samples

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.

$1 \le n, q \le 2 \cdot 10^5$
$1 \le l \le r \le n$
$-10^9 \le x \le 10^9$

\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