← 返回题目列表

Codeforces · 371/D

D. 船只

中文机器翻译题面 查看原题

有一个由 n 个容器组成的系统,一个一个地排列,如下图所示。假设容器编号为1到n,按照从高到低的顺序,第i个容器的体积为ai升。

最初,所有容器都是空的。在一些容器中倒入水。从第 i 个容器溢出的所有水都流向第 (i + 1) 个容器。从第 n 个容器溢出的液体洒在地板上。

你的任务是模拟将水倒入容器中。为此,您需要处理两种类型的查询:

1.向第pi个容器中添加xi升水;
2. 打印第 ki 个容器中水的升数。

当您回复第二个请求时,您可以假设到目前为止倒入的所有水已经溢出容器之间。

输入

第一行包含整数 n — 船只数量 (1 ≤ n ≤ 2·105)。第二行包含 n 个整数 a1, a2, ..., an — 容器的容量 (1 ≤ ai ≤ 109)。容器的容量不一定从顶部容器到底部容器增加(参见第二个示例)。第三行包含整数 m — 查询数量 (1 ≤ m ≤ 2·105)。接下来的 m 行中的每一行都包含一个查询的描述。第一类查询表示为“1 pi xi”,第二类查询表示为“2 ki”(1 ≤ pi ≤ n,1 ≤ xi ≤ 109,1 ≤ ki ≤ n)。

输出

对于每个查询,在一行上打印相应容器中水的升数。

示例

输入 #1

2
5 10
6
1 1 4
2 1
1 2 5
1 1 4
2 1
2 2

输出 #1

4
5
8

输入 #2

3
5 10 8
6
1 1 12
2 2
1 1 6
1 3 2
2 2
2 3

输出 #2

7
10
5