## A Combining Problem

View as PDF

Points: 20
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Given an array $$a$$ of $$N$$ integers, and $$Q$$ queries, support the following operations:

• 1 i k Combine $$k$$ consecutive elements beginning at index $$i$$ (including the element at index $$i$$) into one element in the current array. "Combining" means summing the values of the $$k$$ elements into one.
• 2 i Uncombine the element at index $$i$$ in the current array into its original elements in the original array.
• 3 i k Output the sum of $$k$$ consecutive elements beginning at index $$i$$ (including the element at index $$i$$) in the current array.

$$(1 \le k, i \le 10^5)$$. Let $$M$$ be the number of elements in the current array. Subtract $$M$$ from $$i$$ until $$i$$ is in the range $$[1, M]$$. Let $$L$$ be the number of elements to the right of or at index $$i$$ in the current array. Subtract $$L$$ from $$k$$ until $$k$$ is in the range $$[1, L]$$.

#### Input Specification

The first line will contain two integers, $$N, Q\ (1 \le N, Q \le 10^5)$$.

The second line will contain $$N$$ integers, the values of the original array $$(1 \le a_i \le 10^4)$$.

The next $$Q$$ lines will each contain a valid query as defined above.

#### Output Specification

For each type $$3$$ 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