描述

维护一个数列的区间和
支持插入一个数、区间加、区间翻转

输入

第一行两个正整数N,M
表示初始数列长和操作数
接下来一行N个数
表示初始数列\(v_1\),\(v_2\),...,\(v_N\)
接下来M个操作
A L R V 表示区间[L,R]中每个数加V
R L R 表示翻转区间[L,R]
Q L R 表示询问区间[L,R]的和
I P V 表示插入值V并使之成为数列的第P个数

输出

对每个询问输出一行一个整数为区间和

样例

输入

2 5
1 3
I 2 2
A 1 3 4
Q 2 3
R 2 3
Q 1 2

输出

13
12

范围

80% N,M<=5000
90% N,M<=\(10^4\)
100% 1<=N,M<=\(2\ast 10^5\) 1<=P<=L 1<=L<=R<=L V,\(v_i\)<=1000
(L为数列长度)

限制

2s
256M