문제

Author: Goran Ţuţić

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 Ath to Bth (inclusive) to value X (9, 8, 7, 6, 5, 4, 3, 2, 1) → 1 3 5 0 → (9, 8, 0, 0, 0, 4, 3, 2, 1) 2 A B X Add X to Ath element, 2*X to (A+1)th, …, and (B-A+1)*X to the Bth element (9, 8, 7, 6, 5, 4, 3, 2, 1) → 2 3 5 2 → (9, 8, 9, 10, 11, 4, 3, 2, 1) 3 C X Insert new element with value X immediately before the Cth element (9, 8, 7, 6, 5, 4, 3, 2, 1) → 3 4 100 → (9, 8, 7, 100, 6, 5, 4, 3, 2, 1) 4 A B Find the sum of all elements from Ath to Bth (2, 18, 7, 6, 1, 4, 7, 7, 2) → 4 6 7 → result: 11

입력

The first line of input contains integers N and Q (1 ≤ N, Q ≤ 100 000), 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 ≤ X ≤ 100, 1 ≤ A ≤ B ≤ currentSequenceLength, and 1 ≤ C ≤ currentSequenceLength+1.

출력

For each query of type 4 output one line containing the requested sum. Note: notice that some sums won’t fit into 32-bit integer data type. Author: Goran Ţuţić

예제 입력 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

예제 출력 1

4
0
25

예제 입력 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

예제 출력 2

17
27
100
37