题目描述

有一个高度为 $n$ 层的香槟塔，最高层记为第一层，最底层记为第 $n$ 层，每一层有最大容量，其中第 $i$ 层香槟杯的容量为 $w_i$。

现给定 $q$ 次操作，每次操作为倒香槟或查询中的一个：

• 当 $op=A$ 时，表示在第 $x$ 层的香槟杯中，倒入 $y$ 个单位的香槟。
• 当 $op=Q$ 时，表示查询当前第 $x$ 层的香槟杯中目前有多少单位香槟。

第 $i$ 层香槟杯倒满后，多余的香槟会溢出流向第 $i+1$ 层香槟杯，若第 $i+1$ 层香槟杯也溢出，则会流向第 $i+2$ 层香槟杯，以此类推，最底层香槟杯溢出的香槟不计入询问范围。

输入格式

输入第一行，一个正整数 $n$ 输入第二行，$n$ 个正整数 $w_1,w_2,...,w_n$ 输入第三行，一个正整数 $q$ 接下来 $q$ 行，每行表示一次操作，以 A x y 或 Q x 的形式给出。

输出格式

对于每个询问，输出对应答案，以换行为分割标志。

2
2 5
4
A 1 1
A 2 7
Q 1
Q 2

1
5

数据范围

• 对于 $30\%$ 的数据， $1 \leq n ,q \leq 10$
• 对于 $60\%$ 的数据， $1 \leq n ,q \leq 10^3$
• 对于 $100\%$ 的数据， $1 \leq n ,q \leq 10^5$,$1 \leq x \leq n,1 \leq w_i,y \leq 10^9$