有一个由 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