Description

给出 $n$ 个整数$a[i]$，

$q$ 次操作，每次操作给出$l,r,c$ ，使$a[i]+=c(l\le i\le r)$ .

$q$次操作完成后，输出整个数组$a[i](1\le i\le n)$ .

Format

Input

第一行有两个整数，$n$ 表示数组长度，$q$ 表示操作次数.

第二行有$n$个整数$a[1],a[2],...,a[n]$

接下来$q$ 行，每行有三个整数$l,r,c$ 表示使$a[i]+=c(l\le i\le r)$ .

$1\le n,q,c\le 10^5$

$1\le l\le r\le n$ .

Output

$q$次操作完成后，输出整个数组$a[i](1\le i\le n)$ .

Samples

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

0 0 1 3 4