题目描述

在一个桌子上摆放了 $n$ 个杯子，第 $i(1\le i\le n)$ 个杯子中初始时$a_i$ 毫升水。

小 $A$ 同学负责向杯子中倒水，他总共倒了 $k$ 次，每次会向第 $L$ 个杯子到第 $R$ 个杯子中添加 $P$ 毫升的水 (注意：水只可能增加，不可能减少)。

请问小 $A$ 同学倒了 $k$ 次水之后， 这 $n$ 个杯子每个杯子有多少毫升的水。

输入格式

第一行输入两个正整数 $n,k$, 分别表示杯子的数量和倒水的次数

第二行输入 $n$ 个正整数, 分别表示每个水杯的初始水量

第三行输入 $k$ 次操作, 每次操作输入三个整数 $L,R,P$, 往第 $L$ 个水杯到第 $R$ 个水杯增加水量 $P$ 毫升

输出格式

输出一行共 $n$ 个数, 表示最终每个水杯的水量

8 3
1 2 10 8 1 5 1 1
7 8 12
1 8 4
2 3 12

5 18 26 12 5 9 17 17

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,k \le 10^5,1\le a_i\le 1000,1\le L\le R\le n,1\le p\le 1000$。