Description

Maintain a sequence with a total of $7$ operations:

I. INSERT x n a1 a2 .. an Insert $n$ numbers $a_1 \dots a_n$ after the $x$-th number.

II. DELETE x n Delete $n$ numbers starting from the $x$-th number.

III. REVERSE x n Reverse the interval of $n$ numbers starting from the $x$-th number.

IV. MAKE-SAME x n t Set the $n$ numbers starting from the $x$-th number all to $t$.

V. GET-SUM x n Output the sum of the $n$ numbers starting from the $x$-th number.

VI. GET x Output the value of the $x$-th number.

VII. MAX-SUM x n Output the maximum subarray sum within the $n$ numbers starting from the $x$-th number.

Input Format

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

The second line contains $N$ numbers $A_1 \dots A_N$, representing the initial sequence.

From the third line to line $M+2$, each line contains one operation.

Output Format

Output the result of each GET-SUM, GET, and MAX-SUM operation.

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

-1
10
-5
10

Hint

There are $20$ groups of testdata, each randomly generated.
It is guaranteed that at any time the sequence contains at most $200000$ numbers.
Every input integer is in $[-1000, 1000]$, and any result does not exceed $2^{30}$.

Groups 1–2: $1 \le N \le 5$, $1 \le M \le 10$.

Groups 3–4: $1 \le N \le 10$, $1 \le M \le 20$.

Groups 5–6: $1 \le N \le 20$, $1 \le M \le 50$.

Groups 7–8: $1 \le N \le 50$, $1 \le M \le 100$.

Groups 9–10: $1 \le N \le 100$, $1 \le M \le 500$.

Groups 11–12: $1 \le N \le 1000$, $1 \le M \le 1000$.

Groups 13–14: $1 \le N \le 5000$, $1 \le M \le 2000$.

Groups 15–16: $1 \le N \le 10^4$, $1 \le M \le 5000$.

Groups 17–18: $1 \le N \le 10^5$, $1 \le M \le 10^4$.

Groups 19–20: $1 \le N \le 2 \times 10^5$, $1 \le M \le 2 \times 10^4$.

Translated by ChatGPT 5