问题描述

差分是一种高效处理区间修改问题的算法。给定一个长度为 $n$ 的数组 $a$，有 $m$ 次操作，每次操作会对数组 $a$ 的某个区间 $[l, r]$ 内的所有元素加上一个值 $c$。最后输出经过所有操作后的数组 $a$。

输入格式

• 第一行包含两个整数 $n$ 和 $m$，分别表示数组的长度和操作的次数。
• 第二行包含 $n$ 个整数，表示数组 $a$ 的初始元素。
• 接下来的 $m$ 行，每行包含三个整数 $l$、$r$ 和 $c$，表示将区间 $[l, r]$ 内的所有元素加上 $c$。

输出格式

输出一行，包含 $n$ 个整数，表示经过所有操作后的数组 $a$。

输入输出样例 #1

输入 #1

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

输出 #1

3 4 5 3 4 2

数据范围

• $1 \leq n, m \leq 10^5$
• $-10^9 \leq a_i, c \leq 10^9$
• $1 \leq l \leq r \leq n$