由于某些原因本题仅支持 C++, C++11 语言的提交。

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$ 天之后每个盒子中糖果的数量。

实现细节

你必须引用 candies.h 头文件。

你要实现以下函数：

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]\dots c[n-1]$
• 第 $3$ 行：$q$
• 第 $4+j$ 行（$0\le j\le q-1$）：$l[j]r[j]v[j]$

输出格式

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

• 第 $1$ 行：$s[0]s[1]\dots s[n-1]$

样例一

input

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

output

0 4 13

explanation

考虑如下调用：

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,4,13]$。

数据范围

对于所有数据：

• $1\le n\le 200000$
• $1\le q\le 200000$
• $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$）

时间限制：$4\mathtt{\text{s}}$

空间限制：$2\mathtt{\text{GB}}$