Description

Please write a program to maintain a sequence that supports the following $6$ operations:

Input Format

The first line contains two integers $N$ and $M$, where $N$ is the number of elements in the initial sequence, and $M$ is the number of operations to perform.

The second line contains $N$ numbers describing the initial sequence. Each of the following $M$ lines contains one command; see the table in the Description for the formats.

Output Format

For each $\operatorname{GET-SUM}$ and $\operatorname{MAX-SUM}$ operation in the input, print the result to the output in order, one answer (number) per line.

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

Hint

Constraints

• You may assume that at any time, the sequence contains at least $1$ number.
• The input is guaranteed to be valid, i.e., the specified positions always exist in the sequence.
• For $50\%$ of the testdata, the sequence contains at most $3 \times 10^4$ numbers at any time.
• For $100\%$ of the testdata, the sequence contains at most $5 \times 10^5$ numbers at any time; each number is within $[-10^3, 10^3]$ at any time; $1 \le M \le 2 \times 10^4$; the total count of inserted numbers does not exceed $4 \times 10^6$.

Problem statement provided by @syksykCCC.

Translated by ChatGPT 5