M. Mendocinos Mismanaging Malbec
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

On a mountain in Mendoza there are $$$N$$$ barrels of malbec arranged in a line, numbered from $$$1$$$ to $$$N$$$ from the base of the mountain to the summit. Each barrel has a fixed capacity. At the beginning of a wine season, all barrels are empty.

The season lasts $$$M$$$ days. On each day, exactly one of the following operations occurs:

  • A winemaker pours $$$V$$$ liters of malbec into the $$$B$$$-th barrel. If, after adding the malbec, the amount stored exceeds the barrel's capacity, the excess flows into barrel $$$B-1$$$. If that one also exceeds its capacity, the excess continues into barrel $$$B-2$$$, and so on. If barrel $$$1$$$ also overflows, the excess falls to the floor and is lost.
  • An oenologist takes all the malbec from all barrels between the $$$L$$$-th barrel and the $$$R$$$-th barrel, inclusive. After this operation, all those barrels become empty.
For each operation in which an oenologist takes malbec, you must say how many liters they obtained.
Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 2 \times 10^{5}$$$), the number of barrels and the number of days in the season, respectively.

The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$1 \leq A_i \leq 10^{9}$$$), where $$$A_i$$$ is the capacity of the $$$i$$$-th barrel in liters.

Each of the following $$$M$$$ lines contains three integers and describes an operation:

  • $$$1$$$ $$$B$$$ $$$V$$$ ($$$1 \leq B \leq N$$$, $$$1 \leq V \leq 10^{9}$$$), indicates that a winemaker pours $$$V$$$ liters of malbec into the $$$B$$$-th barrel.
  • $$$2$$$ $$$L$$$ $$$R$$$ ($$$1 \leq L \leq R \leq N$$$), indicates that an oenologist takes all the malbec from the barrels between the $$$L$$$-th and $$$R$$$-th barrel, inclusive.
Output

For each operation of the second type, output a line with an integer indicating the number of liters of malbec the oenologist took.

Example
Input
5 7
3 15 2 10 6
1 4 7
1 5 10
2 3 4
2 1 5
1 1 5
1 2 12
2 1 2
Output
11
6
15
Note

For the example, the following images illustrate how much Malbec there is in each barrel after each operation:

The images after the fourth operation and after the last operation were not included since all barrels are empty and look like those in the first image.