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 to organize an even bigger champagne fountain for the next World Finals. He has already ordered $n$ glass bowls with different capacities to stack on top of each other into a huge glass fountain. However, he is still unsure how to pour the champagne into it. One bottle will not be enough, and 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 a shame.

The $i$th image visualizes the $i$th query of type '+'.

You are tasked with writing a program that simulates pouring champagne into a given fountain. If a bowl in some level is already full, the champagne spills over to the first level below it with a larger capacity. If that level is also full, the champagne spills further down, until it seeps into the ground and is wasted. Bill also wants to know, at certain points in the simulation, how much champagne is in a given level.

The first line has two integers $n$ and $q$ ($1\leq n, q \leq 3 \cdot 10^5$), the number of levels and the number of queries.

The second line has $n$ distinct integers $c$ ($1\leq c \leq 10^9$), the capacity of each level in litres. The levels are given from top to bottom.

Each of the next $q$ lines describes a query. The first symbol $t$ is either '+' or '?'.

• If $t$ is '+', two integers $\ell$ and $x$ follow ($1 \leq \ell \leq n$, $1 \leq x \leq 10^9$). Bill pours $x$ litres of champagne into level $\ell$.
• If $t$ is '?', one integer $\ell$ follows ($1 \leq \ell \leq n$). Bill requests the current amount of champagne in level $\ell$ 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.