A Range Update Problem

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

You are given an array \(a\) of length \(N\). There are \(Q\) updates of the form l r v, which means to add \(v\) to all elements in the subarray \([l, r]\).

You would like to know the array after these updates.

Input Specification

The first line will contain two integers, \(N, Q\ (1 \le N, Q \le 10^5)\).

The second line will contain \(N\) integers, \(a_1, a_2, \ldots, a_N\ (0 \le a_i \le 10^9)\), the initial array.

The next \(Q\) lines will each contain an update of the form described above. It is guaranteed \(1 \le l \le r\) and \(1 \le v \le 10^9\).

Output Specification

Output the array after these updates on a single line.

Subtasks

Subtask [20%]

\(N, Q \le 100\)

Subtask [80%]

No further constraints.

Sample Input

5 4
1 2 3 0 2
1 3 2
1 5 1
3 4 10
2 2 1

Sample Output

4 6 16 11 3

Comments

There are no comments at the moment.