题目描述

小明受邀参加一对新人的婚礼。在婚礼现场，小明看到了一个非常市场的香槟塔，如下图所示。看着新郎新娘打开香槟，缓缓倒入摆好的多层杯塔内，小明也不经幻想起美好的未来。

众所周知，婚礼中新郎新娘会和大家一起玩一些游戏，其中最为常见的就是接亲时对新郎和伴郎的考验。现在，伴娘团根据刚刚的浪漫的香槟塔出了一个问题。

为了简化问题，我们把香槟塔看成如下 $n$ 层塔式的容器模型，对于每个容器，从最高层到最底层分别编号为 $1,2,\dots,n$。

现在会在这些容器中倒上一些香槟，当第 $i$ 层容器倒满时，多余的香槟会流到第 $i+1$ 层中，如果第 $n$ 层容器也满了香槟就会流到外面去（ps：现实生活中我们应杜绝浪费）。新娘团告诉你们第 $i$ 层容器的容量为 $a_i$，比较特殊的是，$a_i$ 不一定递增。

伴娘团想要新郎团队实现下面两种操作 $q$ 次：

1. 往某一个编号为 $x$ 的容器中倒入 $v$ 体积的香槟。
2. 求出某一个编号为 $k$ 的容器中的香槟体积。

新郎将这一个任务交给了作为伴郎的小明，现在小明希望学过编程的你来帮他完成。

输入格式

第一行一个正整数 $n$，表示塔式的层数。

第二行共有 $n$ 个正整数，$a_1,a_2,\dots,a_n$，其中 $a_i$ 表示第 $i$ 层容器的容量。整数之间用空格隔开。

第三行一个正整数 $q$，表示需要执行的操作次数。

接下来 $q$ 行，每行包含若干个整数，表示一个操作，具体如下：

• 操作1: 1 x v，含义: 往 $x$ 编号的容器中倒入 $v$ 体积的香槟。
• 操作2: 2 k，含义: 输出 $k$ 编号容器中的香槟体积。

输出格式

输出包含若干行整数，即为所有操作 $2$ 的结果，对于每一个操作 $2$ 输出一行。

输入输出样例 #1

输入 #1

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

输出 #1

4
5
10

说明/提示

【样例解释】

有 6 次操作：

• 第 $1$ 次操作，往 $1$ 容器倒入 $4$ 体积的香槟，现在两个容器中的香槟从上到下分别为 $4,0$
• 第 $2$ 次操作，输出 $1$ 容器中的香槟为 $4$
• 第 $3$ 次操作，往 $2$ 容器倒入 $5$ 体积的香槟，现在两个容器中的香槟从上到下分别为 $4,5$
• 第 $4$ 次操作，往 $1$ 容器倒入 $100$ 体积的香槟，因为 $1$ 容器容积为 $5$，$2$ 容器容积为 $10$，倒入 $100$ 后，两个容器都会装满，现在两个容器中的香槟从上到下分别为 $5,10$
• 第 $5$ 次操作，输出 $1$ 容器中的香槟为 $5$
• 第 $6$ 次操作，输出 $2$ 容器中的香槟为 $10$

【数据范围】

对于 $30\%$ 的数据，$n,q \le 1000$；

对于 $50\%$ 的数据，$n,q \le 10000$；

对于 $100\%$ 的数据，$n,q \le 10^5,1 \le a_i \le 1000$，并保证对于所有操作 $1$ 有 $1 \le x \le n, 1\le v \le 1000$，对于所有操作 $2$ 有 $1 \le k \le n$。