Given an array of
integers, and
queries, support the following operations:
1 i k
Combineconsecutive elements beginning at index
(including the element at index
) into one element in the current array. "Combining" means summing the values of the
elements into one.
2 i
Uncombine the element at indexin the current array into its original elements in the original array. (i.e. the element at index
in the current array is transformed back into the elements in
that is included in element
)
3 i k
Output the sum ofconsecutive elements beginning at index
(including the element at index
) in the current array.
. Let
be the number of elements in the current array. Subtract
from
until
is in the range
. Let
be the number of elements to the right of or at index
in the current array. Subtract
from
until
is in the range
.
Input Specification
The first line will contain two integers,
.
The second line will contain integers, the values of the original array
.
The next lines will each contain a valid query as defined above.
Output Specification
For each type query, output the answer on its own line.
Sample Input
3 9
1 3 4
1 1 2
3 1 1
3 1 2
2 1
3 2 2
3 2 1
1 2 2
1 1 2
3 10000 100000
Sample Output
4
8
7
3
8
Comments
For operation of type 2, will the index i always be a previously combined index?
If not, should we simply do nothing?
Also, if we have an element that has been combined twice, what should we do? For example, given
1 2 3 4
, then combining to3 7
and further to10
, when uncombining, do we get1 2 3 4
or3 7
?solid question