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 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.
input 5 5 1 2 3 4 5 1 5 5 0 4 4 5 4 5 5 2 1 5 1 4 1 5 output 4 0 25 input 1 7 100 3 1 17 3 2 27 3 4 37 4 1 1 4 2 2 4 3 3 4 4 4 output 17 27 100 37
출처:coci