题目描述

给出一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，接下来有 $m$ 次修改操作。

每次操作给出 $l,r,x$，表示把 $a_l,a_{l+1},\dots,a_r$ 中的每个数都加上 $x$。

请在所有操作结束后输出整个序列。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

接下来 $m$ 行，每行三个整数 $l,r,x$，保证 $1\le l\le r\le n$。

输出格式

输出一行 $n$ 个整数，为所有操作结束后的序列。

输入输出样例 #1

输入 #1

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

输出 #1

2 2 4 4 4

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 2\times 10^5$，$1\le m\le 10^5$，$|a_i|\le 10^9$，$|x|\le 10^9$。