Under construction

Still being built. Things may change

Dynamic Sequence Data Structure

Time limit1sMemory limit128 MB

Summary
Design a data structure supporting range assignment, range arithmetic-progression addition, mid-sequence insertion, and range-sum queries efficiently.
Level

Hard8 of 10

Topics
Segment tree, Array, Implementation
Solved
No attempts yet

Problem

You are given an integer sequence and must process the following four operations in order. Positions are 1-indexed in the current sequence.

FormatDescription
1 A B XChange every number from position A through position B to X.
2 A B XAdd X to position A, 2*X to position A+1, ..., and (B-A+1)*X to position B.
3 C XInsert X immediately before the number at position C. If C is the current sequence size+1, insert X at the end.
4 A BPrint the sum of the numbers from position A through position B.

Given the initial sequence and the list of operations, write a program that prints the result whenever an operation of type 4 appears.

Input

The first line contains N and Q. N is the size of the initial sequence, and Q is the number of operations. (1 <= N, Q <= 100,000)

The second line contains the N elements of the initial sequence, separated by spaces. Each element is a nonnegative integer not greater than 100,000.

The next Q lines contain the operations in order. For operations that contain X, 0 <= X <= 100. For range operations, 1 <= A <= B <= the current sequence size. For insertion operations, 1 <= C <= the current sequence size+1.

Output

For each operation of type 4, print the corresponding range sum on its own line. The sum can exceed the range of a 32-bit integer.

Examples2

  1. Example 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
    Expected output
    4
0
25

  2. Example 2

    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
    Expected output
    17
27
100
37