题目描述

给定一个长度为 $n$ 的数组 $a_1, a_2, \cdots, a_n$，表示初始状态的 $n$ 个元素。接下来有 $m$ 次操作，每个操作包含三个整数 $l_i, r_i, k$，表示将区间 $[l_i, r_i]$ 内的每个元素增加 $k$。

请你输出经过这 $m$ 次操作后数组的最终状态。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示数组的初始值 $a_1, a_2, \cdots, a_n$。

接下来 $m$ 行，每行包含三个整数 $l_i, r_i, k$，满足 $1 \le l_i \le r_i \le n$，表示区间 $[l_i, r_i]$ 内的每个元素增加 $k$。

输出格式

共一行，输出最终数组的 $n$ 个元素，按空格分隔。

样例输入

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

3 3 5 4 6

样例解释

• 第 1 次操作：将区间 $[1, 3]$ 内的元素都增加 $2$，数组变为 $[3, 4, 5, 4, 5]$。
• 第 2 次操作：将区间 $[2, 4]$ 内的元素都增加 $-1$，数组变为 $[3, 3, 4, 3, 5]$。
• 第 3 次操作：将区间 $[3, 5]$ 内的元素都增加 $1$，数组变为 $[3, 3, 5, 4, 6]$。

数据范围

• 对于 $50\%$ 的数据：$n,m \le 1000$
• 对于 $100\%$ 的数据：$1 \le n,m \le 10^5$
• 初始数组元素满足 $1 \le a_i \le 10^4$
• 每次操作中的 $k$ 满足 $-10^4 \le k \le 10^4$