题目描述

由于巨人们的进攻，人类的生活圈已经越来越常。某一年，巨人又开始对南方的围墙发起猛攻，但是南方围墙非常坚固，巨人无法攻进去。不过巨人在某一天感染了一种特殊病毒，这种病毒可以让巨人长高。长高的巨人就可以突破围墙了，这令南方的守城兵长非兄慌，他不断派人把围墙修改以抵挡敌人的进攻。最后巨人终于停止了这一波攻击。士兵长想知道现在每一堵墙有多高。

输入格式

第一行两个数$\red{n，}$$\red{m}$表示有$\red{n}$堵围墙，$\red{m}$次修墙。

接下来一行$\red{n}$个数为围墙的初始高度。

接下来$\red{m}$行每行$\red{3}$个数$\red{L_i,R_i，}$$\red{X_i，}$表示第$\red{L_i}$到$\red{R_i}$堵围墙都增高$\red{X_i}$米。

输出格式

一行$\red{n}$个数：第$\red{i}$个数表示编号为$\red{i}$的墙的最后高度。

样例

输入样例

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

输出样例

2 4 5 6 6

提示

对于$\red{30\%}$的数据：$\red{1 ≤}$ $\red{n}$、$\red{m ≤}$ $\red{1000}$。

对于$\red{60\%}$的数据：$\red{1 ≤}$ $\red{n}$、$\red{m ≤}$ $\red{100000}$。

对于$\red{100\%}$的数据：$\red{1 ≤}$ $\red{n}$、$\red{m ≤}$ $\red{700000，}$$\red{1 ≤}$ $\red{L_i ≤}$ $\red{R_i ≤}$ $\red{n，}$$\red{1 ≤}$ $\red{X_i ≤}$ $\red{1000}$。