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 .
Subtask 1 [10%]
Subtask 2 [10%]
All queries of type appear after all queries of type ; there are no queries of type .
Subtask 3 [30%]
For all queries of type , .
Subtask 4 [50%]
No further constraints.
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 the answer to each type query on separate lines.
5 5 4 5 2 9 3 1 1 2 3 2 1 1 1 2 5 2 3 4 3 5