Description

你需要维护一个长度为 N 的序列，支持 Q 次区间修改，每次将区间 [l,r] 内的数字加 val，最后输出修改之后的序列。

Input

第一行两个整数 N，Q.
第二行 N 个整数，代表序列初始值.
第三行开始连续 Q 行，每行三个整数 l，r，val.

Output

一行输出 N 个数字，代表最后的序列.

Sample Input

5 2
1 2 3 4 5
1 3 1
4 5 1

Sample Output

2 3 4 5 6

Hint

0<=N,Q<=100000
常数尽量小吧，要不很容易被卡.