Description

上周，Bill 第一次为香槟喷泉注满了香槟。 他被香槟从一个酒杯流入另一个酒杯的景象所吸引，决定在下一届世界总决赛上组织一个更大的香槟喷泉。 他已经订购了 $n$ 个容量各不相同的玻璃碗，准备将它们从上到下叠放，组成一个巨大的玻璃喷泉。 然而，他还不确定该如何向喷泉中倒入香槟。 一瓶香槟肯定不够，仅仅从顶部倒入也可能无法填满每一层碗。 Bill 想尝试不同的方式来填满喷泉，但浪费任何香槟都是一种遗憾。

:::align{center}

Bill Poucher（ICPC 执行董事，右侧）。© Huawei，经许可使用

图 F.1：样例输入 2 的示意图。第 $i$ 张图片可视化了第 $i$ 个类型为 '$\texttt{+}$' 的操作。

:::

现在轮到你大显身手了！ 你的任务是编写一个程序，模拟向给定喷泉中倒入香槟的过程。 通过这个程序，Bill 可以模拟向不同层倒入指定量的香槟。 如果某一层的碗已经装满，则多余的香槟会溢出到下方第一个容量更大的碗中。 如果下一个更大容量的碗也已装满，香槟会继续向下溢出，直到最终渗入地面，造成浪费。 此外，在模拟过程中，Bill 还希望随时查询某一层当前的香槟量。

Input Format

输入包括：

• 一行包含两个整数 $n$ 和 $q$（$1\leq n, q \leq 3 \times 10^5$），分别表示层数和操作数。
• 一行包含 $n$ 个互不相同的整数 $c$（$1\leq c \leq 10^9$），表示每层的容量（单位：升）。 各层自上而下给出。
• 接下来 $q$ 行，每行描述一个操作。 首字符 $t$（$t \in \{$'$\texttt{+}$'$,$'$\texttt{?}$'$\}$）表示操作类型。 其余内容依 $t$ 的不同而不同：
  • $t=$'$\texttt{+}$'：后接两个整数 $\ell$ 和 $x$（$1 \leq \ell \leq n$, $1 \leq x \leq 10^9$），表示 Bill 向第 $\ell$ 层倒入 $x$ 升香槟。
  • $t=$'$\texttt{?}$'：后接一个整数 $\ell$（$1 \leq \ell \leq n$），表示 Bill 查询第 $\ell$ 层当前的香槟量。

保证至少有一个类型为 '$\texttt{?}$' 的查询。

Output Format

对于每个类型为 '$\texttt{?}$' 的查询，输出该层当前的香槟量（单位：升）。

4 4
1 2 3 4
+ 1 6
? 4
+ 1 6
? 4

0
4

4 8
2 4 3 5
+ 1 4
? 2
+ 2 3
? 4
+ 3 4
? 4
+ 2 10
? 4

2
1
2
5

Hint

由 ChatGPT 4.1 翻译