TheJobOverflow | Range Updates

Range Updates :

Author

HARSH PRIYADARSHI

Difficulty Level : Easy

Submissions : 143

Asked In : Appdynamics

Marks :10

: 4 | : 0

You are given an Array A of length n. You are then given k queries. Each query contains three integers (l,r,x).

You have to add x to all values from A[l] to A[r] both inclusive. Print the array after the updates are done.

Input

First line contains two values $$$n$$$ $$$k$$$. $$$(1 \le n,k \le 2 ⋅ 10^5)$$$ - number of elements in the array, number of queries.

Next line contains n integers $$$A1,A2,A3...An$$$. $$$(0 \le Ai \le 2⋅10^5)$$$ - the elements of the array.

Next $$$k$$$ lines contain three integers $$$l,r,x$$$. $$$(1 \le l \lt r \le n)$$$ - the range of the update. $$$(-10^6 \le x \le 10^6)$$$ - the value to be added in the range.

Output

Single line containing $$$n$$$ integers of final array A, after the update queries.

Example

Input

5 2
10 20 30 40 50
1 5 10
2 3 -5

Output

20 25 35 50 60

Note

Here, the first query is 1 5 10

So the array becomes 20 30 40 50 60

Next query is 2 3 -5

So the final array becomes 20 25 35 50 60

You need to login to view your submissions.

You need to login to view all submissions.

Language

Result : Executed

Result : Accepted

Test Cases :