There are piles of sand in a line. The
th pile from the left initially has
units of sand. Answer
queries, the
th query contains
integers
,
, and
:
If is
1
: move units of sand from the
th pile to the (
)th pile. (
).
If is
2
: move units of sand from the
th pile to the (
)th pile. (
).
If is
3
: find the total units of sand in all of the piles between pile and
, inclusive. (
).
The queries will never make you remove more sand from a pile than it contains, or move a negative amount of sand.
Constraints
Subtask 1 [40%]
All queries will have =
.
Subtask 2 [60%]
No additional constraints.
Input Specification
The first line contains space-separated integers,
and
.
The second line contains space-separated integers, the
th integer representing the units of sand in the
th pile.
The next lines each contain
space-separated integers:
,
, and
.
Output Specification
For each query with , output a line containing a single integer: the total units of sand in all of the piles between pile
and
, inclusive.
Sample Input
5 6
4 2 10 3 4
3 2 4
1 2 2
2 3 8
3 1 3
2 1 4
3 2 5
Sample Output
15
8
21
Explanation for Sample
The piles are initially .
After the nd query they are
.
After the rd query they are
.
After the th query they are
.
Comments