## Day 1, Problem 2 - Maintaining a Sequence

Please write a program that maintains a sequence, supporting the following 6 operations:

OperationInput FormatDescription
1. Insert`INSERT posi tot c1 c2 … ctot`After the posi-th number in the current sequence, insert a total of tot numbers: c1, c2, …, ctot. Insertion to the beginning of the sequence will have posi equal to 0.
2. Delete`DELETE posi tot`Starting at the posi-th number in the current sequence, delete a total of tot consecutive numbers.
3. Modify`MAKE-SAME posi tot c`Starting at the posi-th number in the current sequence, change all the values of tot consecutive numbers to c.
4. Reverse`REVERSE posi tot`Starting at the posi-th number in the current sequence, reverse the order of tot consecutive numbers.
5. Get Sum`GET-SUM posi tot`Starting at the posi-th number in the current sequence, output the sum of tot consecutive numbers.
6. Max Sum`MAX-SUM`Output the largest sum of any (non-empty) consecutive subsequence of the current sequence.

### Input Format

The first line of input contains two integers N and M, where N is the initial length of the sequence and M is the number of operations.

The second line of input contains N integers, describing the initial sequence.

For the next M lines, each line will contain a command in one of the formats described above.

### Output Format

For each `GET-SUM` or `MAX-SUM` operation in the input, output the result of the query on a separate line.

### Sample Input

```9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
```

```-1
10
1
10
```

### Explanation

Initially, we have the sequence:

`2   -6    3    5    1   -5   -3    6    3`

For the operation GET-SUM 5 4, we must find the sum of the 4 consecutive elements starting at the 5th position, as highlighted in gray below. The answer is 1 + (-5) + (-3) + 6 = -1.

`2   -6    3    5    1   -5   -3    6    3`

For the operation MAX-SUM, we must find the largest sum of any consecutive subsequence, as shown below. The answer is 3 + 5 + 1 + (-5) + (-3) + 6 + 3 = 10.

`2   -6    3    5    1   -5   -3    6    3 `

For the operation INSERT 8 3 -5 7 2, we insert the numbers -5 7 2 after the 8th number in the current sequence. The inserted numbers are highlighted in gray below.

`2   -6    3    5    1   -5   -3    6   -5    7    2    3`

The operation DELETE 12 1 indicates that the 12th number in the sequence must be deleted. In this case, it is the last number.

`2   -6    3    5    1   -5   -3    6   -5    7    2`

For the operation MAKE-SAME 3 3 2, the 3 consecutive numbers starting at the 3rd position are all changed to 2, as depicted below.

`2   -6    3    5    1   -5   -3    6   -5    7    2`

becomes:

`2   -6    2    2    2   -5   -3    6   -5    7    2`

For the operation REVERSE 3 6, we first extract the 6 consecutive elements starting with the 3rd number in the sequence:

`2   -6    2    2    2   -5   -3    6   -5    7    2`

Then, the extracted sequence 2 2 2 -5 -3 6, after being reversed to 6 -3 -5 2 2 2, is reinserted back into the original place:

`2   -6    6   -3   -5    2    2    2   -5    7    2`

For the final operations GET-SUM 5 4 and MAX-SUM, it shouldn't be hard to get the answers 1 and 10.

```                  |←  GET-SUM 5 4  →|
2   -6    6   -3   -5    2    2    2   -5    7    2
|←         MAX-SUM        →|
```

### Scoring

For each test case, your score will be determined as follows:

• If your program prints the correct answers to all GET-SUM operations at the correct locations in the output, then you will score 60% of points.
• If your program prints the correct answers to all MAX-SUM operations at the correct locations in the output, then you will score 40% of points.
• If your program correctly answers both types operations, then you will score 100% of points.

Please note: If your program can only correctly process one type of operation, then ensure that operations of the other type each receive a corresponding line. Otherwise, we cannot guarantee that your score will be accurate.

### Constraints

You may assume that at any given time, the sequence will contain at least 1 number.
The data in the input is guaranteed to be valid, and will always refer to existing positions in the sequence.

In test data worth 50% of the points, the sequence may contain up to 30 000 numbers at any given moment.
In test data worth 100% of the points, the sequence may contain up to 500 000 numbers at any given moment.

In test data worth 100% of the points, the value of any number in the sequence will be in the range [-1000, 1000].
In test data worth 100% of the points, M ≤ 20 000, the sum of all inserted values will not exceed 4 000 000, and the input will not exceed 20MB.

Point Value: 40 (partial)
Time Limit: 2.00s
Memory Limit: 256M