上周，Bill 第一次装满了一个香槟喷泉。看着香槟从一个杯子流向另一个杯子，他感到非常高兴，于是决定为下一届世界总决赛组织一个更大的香槟喷泉。他已经订购了 $n$ 个容量各不相同的玻璃碗，并将它们堆叠在一起，形成一个巨大的玻璃喷泉。然而，他仍然不确定如何将香槟倒入喷泉中。一瓶香槟是不够的，而且仅仅从顶部倒入可能无法填满每一个碗。Bill 想要尝试不同的方式来填满喷泉，但浪费任何香槟都是一种遗憾。

图 F.1：样例输入 2 的示意图。第 $i$ 幅图像展示了第 $i$ 个类型为 '+' 的查询。

现在是你大显身手的时候了！你的任务是编写一个程序，模拟将香槟倒入给定喷泉的过程。通过这个程序，Bill 现在可以模拟向不同的层倒入一定量的香槟。如果某一层中的碗已经装满，那么香槟会溢出到下方第一个容量更大的层中。如果下一个更大的层也满了，香槟会进一步溢出，直到最终渗入地面，从而浪费掉这些好酒。此外，Bill 还想在模拟过程中的某些时刻了解某一层当前有多少香槟。

输入格式

输入包含： 一行，包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 3 \cdot 10^5$)，表示层数和查询次数。 一行，包含 $n$ 个不同的整数 $c$ ($1 \le c \le 10^9$)，表示每一层的容量（单位为升）。这些层按从上到下的顺序给出。 $q$ 行，每行描述一个查询。第一个符号 $t$ ($t \in \{'+', '?'\}$) 描述查询的类型。该行其余部分的格式取决于 $t$： $t = '+'$：后跟两个整数 $\ell$ 和 $x$ ($1 \le \ell \le n, 1 \le x \le 10^9$)，表示 Bill 想要向第 $\ell$ 层倒入 $x$ 升香槟。 * $t = '?'$：后跟一个整数 $\ell$ ($1 \le \ell \le n$)，表示 Bill 请求查询第 $\ell$ 层当前含有的香槟量（单位为升）。

保证至少有一个类型为 '?' 的查询。

输出格式

对于每个类型为 '?' 的查询，输出请求层中当前的香槟量（单位为升）。

样例

样例输入 1

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

样例输出 1

0
4

样例输入 2

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

样例输出 2

2
1
2
5