Loyalty Game

Loyalty Game is a game in which $N$ students, numbered 1 to $N$, take turns drinking all of $X$ liters of liquor in order. Luckily, the students of Hangkong University are very loyal, so each student drinks as much of the liquor passed to them as they can, up to their maximum capacity.

Here, the maximum capacity is the largest amount of liquor a person can drink. When a student drinks up to their maximum capacity, they become drunk, and from then on they forget loyalty and pass the liquor to the next student right away. However, if liquor reaches student $N$ and they become drunk while drinking it, or they are already drunk, all the liquor is thrown away.

Two kinds of queries are given in time order. The queries accumulate.

• 1 $i$ $x$: Person $i$ has $x$ liters of liquor, and the game runs from person $i$ to person $N$. ($1 \leq i \leq N$; $1 \leq x \leq 1\,000\,000\,000$)
• 2 $i$: Print the total amount of liquor student $i$ has drunk so far. ($1 \leq i \leq N$)

The first line contains the number of students $N$ and the number of queries $Q$, separated by a space. ($1 \leq N, Q \leq 100\,000$)

The next $N$ lines each contain the maximum capacity $m_i$ of student $i$. ($1 \leq m_i \leq 10^9$; $1 \leq i \leq N$)

From line $N + 2$, the next $Q$ lines each contain a query in the format described above.

All given numbers are integers.

For each query of type 2, print the answer on its own line, in the order the queries appear.