在 Hyunbin 居住的城市里，每天都会举办一场音乐会。

Hyunbin 讨厌噪音，因此他安装了 $N$ 个隔音屏障，从 $1$ 到 $N$ 依次编号。第 $i$ 个隔音屏障可以吸收 $D_i$ 单位的噪音。在安装好隔音屏障后，他制定了一条规则：未来的所有音乐会只能在两个相邻的隔音屏障之间举办。换句话说，未来的所有音乐会只能在隔音屏障 $c$ 和隔音屏障 $c+1$ 之间举办，其中 $c$ 为满足 $1 \leq c < N$ 的整数。

与 Hyunbin 吸收所有噪音并享受安静生活的计划不同，有时隔音屏障无法承受音乐会产生的全部噪音。假设一场音乐会在隔音屏障 $c$ 和 $c+1$ 之间举办，并产生 $x$ 单位的噪音。隔音屏障 $c$ 仅吸收 $\min(D_c, x)$ 单位的噪音，如果还有未被吸收的噪音，它会传播到屏障 $c-1$。同样地，隔音屏障 $c+1$ 仅吸收 $\min(D_{c+1}, x)$ 单位的噪音，剩余的噪音会传播到屏障 $c+2$。这个过程会重复进行，直到没有剩余噪音，或者有噪音未被吸收但已经没有隔音屏障可以继续吸收为止。

在每场音乐会结束后，Hyunbin 决定将这 $N$ 个隔音屏障中每一个的吸音能力提升其所吸收的噪音量。因此，如果隔音屏障 $k$ 吸收了 $x$ 单位的噪音，在音乐会结束后，它的吸音能力会立即变为 $D_k+x$。

Hyunbin 会执行以下两种操作之一，共 $Q$ 次。

• $1$ $c$ $x$：在隔音屏障 $c$ 和 $c+1$ 之间举办一场产生 $x$ 单位噪音的音乐会，随后隔音屏障的吸音能力会相应提升。（$1\leq c
• $2$ $c$：Hyunbin 测量屏障 $c$ 的吸音能力。（$1\leq c \leq N$）

每次执行类型 $2$ 的操作时，输出该隔音屏障的吸音能力。

输入格式

输入的第一行包含一个整数 $N$，表示 Hyunbin 安装的隔音屏障数量。（$2\leq N \leq 200\,000$）

输入的第二行包含 $N$ 个空格分隔的整数，每个整数表示 $D_i$，即每个隔音屏障的吸音能力。（$1\leq D_i \leq 10^9$）

输入的第三行包含一个整数 $Q$，表示 Hyunbin 执行的操作次数。（$1\leq Q \leq 200\,000$）

接下来的 $Q$ 行，每行包含一个操作，格式与题目描述中所写相同。保证输入中至少会给出一个类型 2 的操作。

所有输入值均为整数。

输出格式

按顺序输出 Hyunbin 执行的所有类型 $2$ 操作的结果，每行一个。

样例

输入样例 1

6
5 1 2 4 7 3
5
1 2 1
2 3
1 4 7
2 3
2 5

输出样例 1

3
6
14