Ranged Incrementation

You are given an array A of size \(n\) where every element is initially zero. You are also given \(m\) operations. Each operation is described by three integers \(l\), \(r\), and \(k\) and means that you should add \(k\) to every element of the array with indices in the interval \([l, r]\) (1-indexed).

Formally, for every operation, for every index \(j\) satisfying \(l \le j \le r\), update \(A_j = A_j + k\). After performing all operations, output the final state of the array.

Hint: An efficient way to handle many range updates is to use a difference array. The difference array \(D\) of \(A\) is defined by \(D_1 = A_1\) and \(D_i = A_i - A_{i-1}\) for \(i > 1\). An update of adding \(k\) to the range \([l, r]\) can be done in \(O(1)\) time by setting \(D_l = D_l + k\) and \(D_{r+1} = D_{r+1} - k\) (if \(r+1 \leq n\)), then recovering the array \(A\) using prefix sums.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m
l1 r1 k1
l2 r2 k2
... 
lm rm km

Here, \(n\) is the size of the array and \(m\) is the number of operations. For each operation, \(l\) and \(r\) denote the starting and ending indices (1-indexed) of the range to update and \(k\) is the increment value.

outputFormat

After applying all the operations, output the final state of the array as a single line of \(n\) space-separated integers. The output should be written to standard output (stdout).

5 3
1 3 2
2 5 3
1 2 1

3 6 5 3 3