描述

给你一个长为N的数字序列A1,A2,...,AN
你需要维护区间和
支持三种修改：插入一个数(I)，删除一段数(D)，将一段数翻转(R)

输入

第一行两个数N, M
第二行N个数为A1,A2,...,AN
接下来M行，每行若干个数，表示一个操作
I ix iy 表示在第x个数后插入值y
D dx dy 表示删除第x个至第y个数
R rx ry 表示将第x个至第y个数翻转，例如345变成543
Q qx qy 表示询问第x个至第y个数的和

输出

对每个询问，一行一个数表示所问区间的数值和

样例

输入

5 7
1 2 3 4 5
I 2 7
I 0 1
Q 1 4
R 3 5
R 5 7
D 7 7
Q 4 6

输出

11
16

范围

40% N,M<=5 1<=Ai,iy<=10
60% N,M<=1000 1<=Ai,iy<=1000
100% 1<=N,M<=\(10^6\) 1<=Ai,iy<=5000 0<=ix<=Len 1<=dx<=dy<=Len 1<=rx<=ry<=Len 1<=qx<=qy<=Len
(Len表示当时序列长度)

限制

3000ms
128M