题目描述

对于给定的长度为 $n$ 的数组 $\{a_1,a_2,\dots,a_n\}$ ，你需要维护：

区间修改：将 $[l,r]$ 这个区间中的全部元素增加 $x$ ；

在全部修改完成后，直接输出最终的数组。

本题数据量过大，请使用较快的 IO 方式

输入格式

第一行输入两个整数 $n,q \left( 1 \leq n,q \leq 5 \times 10^5\right)$ 代表数组中的元素数量、操作次数。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n \left( -10^7 \leq a_i \leq 10^7 \right)$ 代表初始数组。

此后 $q$ 行，每行输入三个整数 $l, r,d \left( 1 \leq l \leq r \leq n;\ -10 ^7 \leq d \leq 10^7 \right)$ 代表一次修改。

输出格式

在一行上输出 $n$ 个整数，代表最终的数组。

输入样例

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

输出样例

-2 -2 1 3 -2 1

说明/提示

对于第一次操作，数组变为 $\{{\color{red}{-2, -2, 1, 2, -2, 1}} \}$（全局修改）；

对于第二次操作，数组变为 $\{-2, -2, 1, {\color{red}{3}}, -2, 1 \}$（单点修改）。