F. update range
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

you have an array $$$a$$$ of size $$$n$$$, and you need to answer $$$q$$$ queries. each query need you to add the $$$val$$$ to all numbers from index $$$L$$$ to index $$$R$$$.

Input

the first line contains two integer $$$n$$$ the size of array, and $$$q$$$ number of queries, $$$(1 \le n , q \le 10^5)$$$.

The second line contains $$$n$$$ numbers $$$a_i (0 \le a_i \le 10^9)$$$.

the next $$$q$$$ lines contains $$$L,R,val (1 \le L \le R \le n , 1 \le val \le 10^9)$$$.

Output

print the array after updates.

Example
Input
5 3
1 0 1 0 1
1 2 1
3 5 3
1 5 2
Output
4 3 6 5 6