数列

题目描述

维护一个数列,共 $7$ 种操作: I. `INSERT x n a1 a2 .. an` 在第 $x$ 个数后插入 $n$ 个数分别为 $a_1\dots a_n$。 II. `DELETE x n` 删除第 $x$ 个数开始的 $n$ 个数。 III. `REVERSE x n` 翻转第 $x$ 个数开始的 $n$ 个数的区间。 IV. `MAKE-SAME x n t` 将第 $x$ 个数开始的 $n$ 个数统一改为 $t$。 V. `GET-SUM x n` 输出第 $x$ 个数开始的 $n$ 个数的和。 VI. `GET x` 输出第 $x$ 个数的值。 VII. `MAX-SUM x n` 输出第 $x$ 个数开始的 $n$ 个数的最大连续子序列和。

输入输出格式

输入格式


第一行为 $N$,$M$,$N$ 表示初始序列中数的个数,$M$ 表示操作的个数。 第二行为 $N$ 个数 $A_1\dots A_n$,表示初始序列。 第三行到第 $M+2 $行,每行一个操作。

输出格式


输出每个`GET-SUM`,`GET`,`MAX-SUM`操作的结果。

输入输出样例

输入样例 #1

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

-1
10
-5
10

说明

共 $20$ 组数据,每组数据随机生成, 保证每个时刻数列里的数不超过 $200000$ 个, 任何一个输入的数字均在 $-1000\sim1000$之间,结果不超过 $2^{30}$。 第 $1\sim2$ 组 $\quad1\le N\le 5$,$1\le M\le 10$。 第 $3\sim4$ 组 $\quad1\le N\le 10$,$1\le M\le 20$。 第 $5\sim6$ 组 $\quad1\le N \le 20$,$1\le M\le 50$。 第 $7\sim8$ 组 $\quad1\le N\le 50$,$1\le M\le 100$。 第 $9\sim10$ 组 $\quad1\le N\le 100$,$1\le M\le 500$。 第 $11\sim12$ 组 $\quad 1\le N\le 1000$,$1\le M\le 1000$。 第 $13\sim14$ 组 $\quad1\le N\le 5000$,$1\le M\le 2000$。 第 $15\sim16$ 组 $\quad1\le N\le 10^4$,$1\le M\le 5000$。 第 $17\sim18$ 组 $\quad1\le N\le 10^5$,$1\le M\le 10^4$。 第 $19\sim20$ 组 $\quad1\le N\le 2\times 10^5$,$1\le M\le 2\times 10^4$。