题目描述

taorunz 平时最喜欢的东西就是可移动存储器了…… 只要看到别人的可移动存储器，他总是用尽一切办法把它里面的东西弄到手。

突然有一天，taorunz 来到了一个密室，里面放着一排可移动存储器，存储器里有非常珍贵的 OI 资料…… 不过比较特殊的是，每个存储器上都写着一个非负整数。taorunz 很高兴，要把所有的存储器都拿走。（taorunz 的智商高达 $500$，他一旦弄走了这里的所有存储器，在不久到来的 AHOI 和 NOI 中…… 你懂的）不过这时有一个声音传来：“你只能拿走这里的一个存储器，而且还不能直接拿，你需要指定一段区间 $[l, r]$，满足 $l < r$，然后在第 $l$ 个和第 $r$ 个存储器之间选一个拿走，你能获得的知识增加量等于区间 $[l, r]$ 中所有存储器上写的整数的次大值与你拿走的这个存储器上写的整数作按位异或运算的结果。”

问题是，这里的可移动存储器数量太多，而且，它们还在不断地发生变化，有时候天上会掉下来一个新的存储器，并插入到这一排存储器中，有时候某个存储器会不明原因消失，有时候某个存储器上写的整数变化了。taorunz 虽然智商很高，但也无法应对如此快的变化，他指定了许多段区间，让你帮他找出如果在这个区间中拿走存储器，他能获得的最多的知识是多少。

输入格式

第一行两个整数 $n$、$m$，表示一开始的存储器数和后面发生的事件数。

第二行 $n$ 个非负整数，表示一开始从左到右每个存储器上写的数字。注意，存储器从 $0$ 开始编号，也就是最左边的存储器是第 $0$ 个。

接下来 $m$ 行，每行描述一个事件，有 $4$ 种可能的事件：

1. I x y：表示天上掉下来一个写着数字 $y$ 的存储器，并插入到原来的第 $x$ 个存储器之前，如果 $x$ 等于原来存储器的个数，则插入到末尾；

2. D x：表示第 $x$ 个存储器消失；

3. C x y：表示第 $x$ 个存储器上写的数字变为 $y$；

4. F l r：表示 taorunz 指定区间 $[l, r]$，让你告诉他最多能获得多少知识。

注意，本题强制在线，也就是事件中出现的所有数字都进行了加密，数字 $s$ 表示的真实值是：

对于 I、D、C 事件中的 $x$ 及 F 事件中的 $l$、$r$：$(s+last\_ans) \mod n_0$；

对于 I、C 事件中的 $y$：$(s+last\_ans) \mod 1\ 048\ 576$。

其中 $n_0$ 为目前存储器个数，$last\_ans$ 为上一个 F 事件的结果，如果前面尚未发生 F 事件，则 $last\_ans = 0$。

输出格式

对于每个 F 事件，输出结果。

5 10
2 6 3 8 7
F 1 4
I 2 1048565
I 0 1048566
D 3
F 3 0
I 3 1048569
D 5
C 1 1048570
F 1 2
F 2 1

15
7
4
7

数据规模与约定

• 对于 $100\%$ 的数据，$1 \leq n, m \leq 10^5$。所有 F 事件满足 $l<r$。
• 本题共有 $5$ 组数据，除 $1$ 组为随机数据外，其它数据均为人工构造。

题目来源

By mato_no1