Flowing Fountain

문제

Last week, Bill filled a champagne fountain for the first time. Delighted by the champagne pouring from one glass into another, he decided that he wants to organize an even bigger champagne fountain for the next World Finals. He already ordered $nn$ glass bowls with different capacities to stack on top of each other to form a huge glass fountain. However, he is still unsure how to pour the champagne into the fountain. One bottle will not be enough and just pouring from the top might not fill every bowl. Bill wants to try out different ways to fill the fountain, but wasting any champagne would be such a shame.

Figure F.1: Illustration of Sample Input 2. The $ii$th image visualizes the $ii$th query of type '+'.

This is your time to shine! You are tasked with writing a program that simulates the process of pouring champagne into a given fountain. With this program, Bill can now pretend to pour certain amounts of champagne into different levels. If a bowl in some level is already filled up, then the champagne spills over to the first level below it with larger capacity. If the next larger level is also filled, the champagne spills over even further until eventually seeping into the ground, wasting the good champagne. Additionally, Bill also wants to know at some times during the simulation process how much champagne currently is in a certain level.

입력

The input consists of:

• One line with two integers $nn$ and $qq$ ($1\le n,q\le 3\cdot {10}^{5}1\backslash leq\; n,\; q\; \backslash leq\; 3\; \backslash cdot\; 10^5$), the number of levels and the number of queries.
• One line with $nn$ distinct integers $cc$ ($1\le c\le {10}^{9}1\backslash leq\; c\; \backslash leq\; 10^9$), the capacity of each level in litres. The levels are given in order from top to bottom.
• $qq$ lines, each describing a query. The first symbol $tt$ ($t\in \{t\; \backslash in\; \backslash \{$'+', '?'$\}\backslash \}$) describes the type of the query. The format of the rest of the line depends on $tt$:
  • $t=t=$'+': Two integers $\mathrm{\ell }\backslash ell$ and $xx$ follow ($1\le \mathrm{\ell }\le n1\; \backslash leq\; \backslash ell\; \backslash leq\; n$, $1\le x\le {10}^{9}1\; \backslash leq\; x\; \backslash leq\; 10^9$), the level into which Bill wants to pour $xx$ litres of champagne.
  • $t=t=$'?': One integer $\mathrm{\ell }\backslash ell$ follows ($1\le \mathrm{\ell }\le n1\; \backslash leq\; \backslash ell\; \backslash leq\; n$), the level for which Bill requests the current amount of champagne in litres.

It is guaranteed that there is at least one query of type '?'.

출력

For each query of type '?', output the amount of champagne in the requested level in litres.

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