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 $A^{\text{th}}$ to $B^{\text{th}}$ (inclusive) to value $X$.	$(9,8,7,6,5,4,3,2,1)\to 1350\to (9,8,0,0,0,4,3,2,1)$
2 A B X	Add $X$ to $A^{\text{th}}$ element, $2X$, to $(A+1{)}^{\text{th}}$, …, and $(B-A+1)X$ to the $B^{\text{th}}$ element.	$(9,8,7,6,5,4,3,2,1)\to 2352\to (9,8,9,10,11,4,3,2,1)$
3 C X	Insert new element with value $X$ immediately before the $C^{\text{th}}$ element.	$(9,8,7,6,5,4,3,2,1)\to 34100\to (9,8,7,100,6,5,4,3,2,1)$
4 A B	Find the sum of all elements from $A^{\text{th}}$ to $B^{\text{th}}$.	$(2,18,7,6,1,4,7,7,2)\to 467\to$ result: $11$

Input Specification

The first line of input contains integers $N$ and $Q$ $(1\le N,Q\le 100000)$, 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 $100000$ that are separated by a single space. The following $Q$ lines contain queries in the format described above. In all queries, $1\le X\le 100$, $1\le A\le B\le \text{currentSequenceLength}$, and $1\le C\le \text{currentSequenceLength}+1$.

Output Specification

For each query of type $4$, 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