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 |
|
2 A B X |
Add |
|
3 C X |
Insert new element with value |
|
4 A B |
Find the sum of all elements from |
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