数列

题目描述

维护一个数列,共7种操作: 1 INSERT x n a1 a2 .. An 在第x个数后插入n个数分别为a1 .. an; 2 DELETE x n 删除第x个数开始的n个数; 3 REVERSE x n 翻转第x个数开始的n个数的区间; 4 MAKE-SAME x n t 将第x个数开始的n个数统一改为t; 5 GET-SUM x n 输出第x个数开始的n个数的和; 6 GET x 输出第x个数的值; 7 MAX-SUM x n 输出第x个数开始的n个数的最大连续子序列和。

输入输出格式

输入格式


第1行为N,M,N表示初始序列中数的个数,M表示操作的个数。 第2行为N个数a1 .. An,表示初始序列。 第3行到第M+2行,每行一个操作。

输出格式


输出5 GET-SUM,6 GET,7 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~1000之间,结果不超过2^30。 第1~2组1≤N≤51≤M≤10 第3~4组1≤N≤101≤M≤20 第5~6组1≤N≤201≤M≤50 第7~8组1≤N≤501≤M≤100 第9~10组1≤N≤1001≤M≤500 第11~12组1≤N≤10001≤M≤1000 第13~14组1≤N≤50001≤M≤2000 第15~16组1≤N≤100001≤M≤5000 第17~18组1≤N≤1000001≤M≤10000 第19~20组1≤N≤2000001≤M≤20000