#P1793. 进击的巨人(giant)

进击的巨人(giant)

【题目描述】

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

【输入格式】

第一行两个数n,m表示有n堵围墙,m次修墙

接下来一行n个数为围墙的初始高度。

接下来m行每行3个数Li,Ri,Xi,表示第Li到Ri堵围墙都增高Xi米

【输出格式】

一行n个数:第i个数表示编号为i的墙的最后高度。

【样例数据】

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

【数据范围】

对于30%的数据:1 ≤ n、m ≤ 1000。

对于60%的数据:1 ≤ n、m ≤ 100000。

对于100%的数据:1 ≤ n、m ≤ 700000,1 ≤ Li ≤ Ri ≤ n,1 ≤ Xi ≤ 1000。