题目背景

滥用本题评测将被封号

由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。

题目描述

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

Khong 阿姨花了 $q$ 天时间准备糖果盒。在第 $j$ 天 $(0 \leq j \leq q - 1)$，她根据三个整数 $l[j]$、 $r[j]$ 和 $v[j]$ 执⾏操作，其中 $0 \leq l[j] \leq r[j] \leq n - 1$ 且 $v[j] \neq 0$。对于每个编号满⾜ $l[j] \leq k \leq 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$ 天之后每个盒⼦中糖果的数量。

输入格式

实现细节

你要实现以下函数：

std::vector<int> distribute_candies(
  	std::vector<int> c, std::vector<int> l, 
  	std::vector<int> r, std::vector<int> v)

• $c$：⼀个⻓度为 $n$ 的数组。 对于 $0 \leq i \leq n - 1$, $c[i]$ 表⽰盒⼦ $i$ 的容量。

• $l$、 $r$ 和 $v$：三个⻓度为 $q$ 的数组。 在第 $j$ 天, 对于 $0 \leq j \leq q - 1$，Khong 阿姨执⾏由整数 $l[j]$、 $r[j]$ 和 $v[j]$ 决定的操作，如题⾯所述。

输出格式

• 该函数应该返回⼀个⻓度为 $n$ 的数组。⽤ $s$ 表⽰这个数组。 对于 $0 \leq i \leq n - 1$， $s[i]$ 应为 $q$ 天以后盒⼦ $i$ 中的糖果数量。

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

0 4 13

提示

例 1

考虑如下调⽤： 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] ≠ 0$（对所有 $0 \le j \le q - 1$）

子任务

1. （$3$ 分） $n, q \leq 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 \leq j \leq q - 1$）
5. （$33$ 分） 没有额外的约束条件。

评测程序⽰例

评测程序⽰例读⼊如下格式的输⼊：

• 第 $1$ ⾏: $n$
• 第 $2$ ⾏: $c[0] ~ c[1] ~ \cdots ~ c[n - 1]$
• 第 $3$ ⾏: $q$
• 第 $4 + j$ ⾏ ( $0 \leq j \leq q - 1$): $l[j] ~ r[j] ~ v[j]$

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

第 $1$ ⾏: $s[0] ~ s[1] ~ \cdots ~ s[n - 1]$