## Overflow

View as PDF

Points: 30 (partial)
Time limit: 1.4s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Joe is an economical man and he has found a new scheme to save some money! Joe wants to save money on his water bill, so he decides to collect rainwater. Joe has a row of water containers, all initially empty and each with a maximum capacity of liters of water. The containers are connected in such a way that when container overflows, the excess liquid flows to container . When container overflows, the extra water magically disappears. Joe wishes to gather information about the efficacy of his setup, and so he has prepared queries of the following types:

• : Rainfall arrives, and liters of water falls directly into each container from position to inclusive.
• : Joe changes the maximum capacity of bucket to . If the volume decreases, any resulting overflow passes on to bucket as usual.
• : Joe wishes to know the current volume of water being held in container .

#### Constraints

All queries of type appear after all queries of type ; there are no queries of type .

For all queries of type , .

No further constraints.

#### Input Specification

The first line will contain and , the number of containers and number of queries respectively.

The second line will contain space-separated integers, .

The next lines will contain queries of the form mentioned in the problem description.

#### Output Specification

Output the answer to each type query on separate lines.

#### Sample Input

5 5
4 5 2 9 3
1 1 2 3
2 1 1
1 2 5 2
3 4
3 5

#### Sample Output

4
2