B. 年底查账

姬老爷在金陵有着极为富足的产业，商行足足占据了一条街。年关将近，姬老爷决定对所有商行进行一次查账。

姬老爷总共有$n$家商行，都分布在一条长街上排成一排。最初每家商行都有一定的本金，之后姬老爷一共进行了$m$次动账。每次动账姬老爷都会从若干家店铺中提取出等量的银钱用作支出，或是将最近的收入分摊到若干店铺。为了方便起见，姬老爷每次都选了若干连续的店铺做调动。现在，姬老爷想知道每家店铺剩余的银钱的盈亏情况。

第一行输入两个正整数$n$和$m$，代表了姬老爷的店铺数量和动账次数。$(1\leq n,m\leq 10^6)$

第二行一共$n$个正整数$a_i$，表示每家店铺初始的本金。$(1\leq a_i\leq 10^{12})$

接下来一共$m$行，每行三个正整数$b_i,c_i,d_i$，表明第$i$次动账涉及到了从第$b_i$家店铺开始的一共$c_i$家店铺，每家店铺动账的银钱数目为$d_i$，其中$d_i>0$表示收入，$d_i<0$表示支出。$(1\leq b_i\leq n,1\leq b_i+c_i\leq n,-10^{12}\leq d_i\leq 10^{12})$

输出共一行包含$n$个正整数，表明每家店铺最终的账目。正数表示盈余，负数表示亏损。

输入样例

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

输出样例

5 7 -4 3 4