Mirko got tired of implementing all kinds of data structures for different tasks. So, he decided to come up with the ultimate structure, one that will allow him to manipulate with his favorite number sequence.
Help him!
Mirko will give you his number sequence, and a sequence of queries you must execute. Each query either asks for information, or modifies the existing sequence. Possible query types are listed below.
Query type | Description | Example |
---|---|---|
1 A B X |
Set all elements from to (inclusive) to value . | |
2 A B X |
Add to element, , to , …, and to the element. | |
3 C X |
Insert new element with value immediately before the element. | |
4 A B |
Find the sum of all elements from to . | result: |
Input Specification
The first line of input contains integers and , the starting sequence length and the number of queries. The following line contains the starting sequence. Sequence consists of non-negative integers not greater than that are separated by a single space. The following lines contain queries in the format described above. In all queries, , , and .
Output Specification
For each query of type , output one line containing the requested sum.
Note: some sums won't fit into a 32-bit integer.
Sample Input 1
5 5
1 2 3 4 5
1 5 5 0
4 4 5
4 5 5
2 1 5 1
4 1 5
Sample Output 1
4
0
25
Sample Input 2
1 7
100
3 1 17
3 2 27
3 4 37
4 1 1
4 2 2
4 3 3
4 4 4
Sample Output 2
17
27
100
37
Comments