[NOI2005]维修数列

请编写一个程序，维护一个整数数列，并支持以下 $6$ 种操作：

• INSERT posi tot c1 ... ctot：在当前数列的前 $posi$ 个数之后插入 $tot$ 个数 $c_1,\ldots,c_{tot}$。当 $posi=0$ 时，表示在数列最前端插入。
• DELETE posi tot：从当前数列的第 $posi$ 个数开始，删除连续的 $tot$ 个数。
• MAKE-SAME posi tot c：将当前数列中从第 $posi$ 个数开始的连续 $tot$ 个数全部修改为 $c$。
• REVERSE posi tot：将当前数列中从第 $posi$ 个数开始的连续 $tot$ 个数翻转。
• GET-SUM posi tot：求当前数列中从第 $posi$ 个数开始的连续 $tot$ 个数之和。当 $tot=0$ 时，结果为 $0$。
• MAX-SUM：求当前数列的最大连续子列和。连续子列必须非空；当数列为空时，结果为 $0$。

对于 INSERT 操作，$posi$ 表示插入位置之前已有的元素个数，位置从 $0$ 开始计数。对于其余操作，$posi$ 表示数列中从 $1$ 开始计数的位置。

所有操作的参数在执行时均满足以下条件：

• INSERT：$0\le posi\le$ 当前数列长度，且 $tot\ge 1$。
• DELETE、MAKE-SAME、REVERSE：$posi\ge 1$、$tot\ge 1$，且待操作的连续区间完全位于当前数列内。
• GET-SUM：$1\le posi\le$ 当前数列长度 $+1$，且 $tot\ge 0$。当 $tot>0$ 时，待求和的连续区间完全位于当前数列内。
• MAKE-SAME 中的 $c$ 为要赋给区间内所有元素的整数。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示初始数列的长度和操作数。

第二行包含 $N$ 个整数，描述初始数列。

接下来 $M$ 行，每行包含一条命令，格式为以下形式之一：

• INSERT posi tot c1 ... ctot
• DELETE posi tot
• MAKE-SAME posi tot c
• REVERSE posi tot
• GET-SUM posi tot
• MAX-SUM

输出格式

对于每个 GET-SUM 或 MAX-SUM 操作，输出一行，表示该操作的答案。

样例输入

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

数据范围

• $M\le 2\times 10^4$；
• 任意时刻，数列中最多包含 $5\times 10^5$ 个数；
• 数列中的每个整数均在区间 $[-10^3,10^3]$ 内；
• 所有 INSERT 操作插入的数字总数不超过 $4\times 10^6$；
• 输入文件大小不超过 $20\ \mathrm{MB}$。

来源与许可

本题为 NOI 2005 试题「维修数列」，题面与测试数据整理自 BZOJ。

样例 1

输入

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