题目描述

Khong 阿姨正在给附近一所学校的学生准备 $n$ 盒糖果。盒子的编号分别为 $0$ 到 $n - 1$，开始时盒子都为空。第 $i$ 个盒子（$0 \le i \le n - 1$）至多可以容纳 $c[i]$ 块糖果（容量为 $c[i]$）。

Khong 阿姨花了 $q$ 天时间准备糖果盒。在第 $j$ 天（$0 \le j \le q - 1$），她根据三个整数 $l[j]$、$r[j]$ 和 $v[j]$ 执行操作，其中 $0 \le l[j] \le r[j] \le n - 1$ 且 $v[j] \ne 0$。对于每个编号满足 $l[j] \le k \le r[j]$ 的盒子 $k$：

• 如果 $v[j] > 0$，Khong 阿姨将糖果一块接一块地放入第 $k$ 个盒子，直到她正好放了 $v[j]$ 块糖果或者该盒子已满。也就是说，如果该盒子在这次操作之前已有 $p$ 块糖果，那么在这次操作之后盒子将有 $\min{(c[k], p + v[j])}$ 块糖果。
• 如果 $v[j] < 0$，Khong 阿姨将糖果一块接一块地从第 $k$ 个盒子取出，直到她正好从盒子中取出 $-v[j]$ 块糖果或者该盒子已空。也就是说，如果该盒子在这次操作之前已有 $p$ 块糖果，那么在这次操作之后盒子将有 $\max{(0, p + v[j])}$ 块糖果。

你的任务是求出 $q$ 天之后每个盒子中糖果的数量。

---

实现细节

你要实现以下函数：

int[] distribute_candies(int[] c, int[] l, int[] r, int[] v)

• c：一个长度为 $n$ 的数组。对于 $0 \le i \le n - 1$，$c[i]$ 表示盒子 $i$ 的容量。
• l、r 和 v：三个长度为 $q$ 的数组。在第 $j$ 天，对于 $0 \le j \le q - 1$，Khong 阿姨执行由整数 $l[j]$、$r[j]$ 和 $v[j]$ 决定的操作，如题面所述。

该函数应该返回一个长度为 $n$ 的数组。用 $s$ 表示这个数组。对于 $0 \le i \le n - 1$，$s[i]$ 应为 $q$ 天以后盒子 $i$ 中的糖果数量。

---

评测程序示例

评测程序示例读入如下格式的输入：

第 1 行: n
第 2 行: c[0] c[1] ... c[n - 1]
第 3 行: q
第 4 + j 行 (0 ≤ j ≤ q - 1): l[j] r[j] v[j]

评测程序示例按照以下格式打印你的答案：

第 1 行: s[0] s[1] ... s[n - 1]

---

样例

输入：

3
10 15 13
2
0 2 20
0 1 -11

输出：

0 4 13

考虑如下调用：

distribute_candies([10, 15, 13], [0, 0], [2, 1], [20, -11])

这表示盒子 $0$ 的容量为 $10$ 块糖果，盒子 $1$ 的容量为 $15$ 块糖果，盒子 $2$ 的容量为 $13$ 块糖果。

• 在第 $0$ 天结束时，盒子 $0$ 有 $\min{(c[0], 0 + v[0])} = 10$ 块糖果，盒子 $1$ 有 $\min{(c[1], 0 + v[0])} = 15$ 块糖果，盒子 $2$ 有 $\min{(c[2], 0 + v[0])} = 13$ 块糖果。
• 在第 $1$ 天结束时，盒子 $0$ 有 $\max{(0, 10 + v[1])} = 0$ 块糖果，盒子 $1$ 有 $\max{(0, 15 + v[1])} = 4$ 块糖果。因为 $2 > r[1]$，盒子 $2$ 中的糖果数量没有变化。

每一天结束时糖果的数量总结如下：

天	盒子 0	盒子 1	盒子 2
0	10	15	13
1	0	4

就此情况，函数应该返回 [0, 4, 13]。

---

数据范围与提示

对于所有数据：

• $1 \le n \le 200\,000$
• $1 \le q \le 200\,000$
• $1 \le c[i] \le 10^9$（对所有 $0 \le i \le n - 1$）
• $0 \le l[j] \le r[j] \le n - 1$（对所有 $0 \le j \le q - 1$）
• $-10^9 \le v[j] \le 10^9$，$v[j] \ne 0$（对所有 $0 \le j \le q - 1$）

---

子任务

子任务	分值	特殊限制
1	3	$n, q \le 2000$
2	8	$v[j] > 0$（对所有 $0 \le j \le q - 1$）
3	27	$c[0] = c[1] = \cdots = c[n - 1]$
4	29	$l[j] = 0$ 和 $r[j] = n - 1$（对所有 $0 \le j \le q - 1$）
5	33	没有额外的约束条件

---

注意：在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 11 及以上）

请在提交源代码前添加 #include "candies.h"。