题面

题目描述

从前有$n$只跳蚤排成一行做早操，每只跳蚤都有自己的一个弹跳力$a_i$。跳蚤国王看着这些跳蚤国欣欣向荣的情景，感到非常高兴。这时跳蚤国王决定理性愉悦一下，查询区间$k$小值。他每次向它的随从伏特提出这样的问题: 从左往右第$x$个到第$y$个跳蚤中，$a_i$第$k$小的值是多少。

这可难不倒伏特，他在脑袋里使用函数式线段树前缀和的方法水掉了跳蚤国王的询问。

这时伏特发现有些跳蚤跳久了弹跳力会有变化，有的会增大，有的会减少。

这可难不倒伏特，他在脑袋里使用树状数组套线段树的方法水掉了跳蚤国王的询问。（orz 主席树）

这时伏特发现有些迟到的跳蚤会插入到这一行的某个位置上，他感到非常生气，因为……他不会做了。

请你帮一帮伏特吧。

快捷版题意：带插入、修改的区间k小值在线查询。

输入输出格式

输入格式

第一行一个正整数$n$，表示原来有$n$只跳蚤排成一行做早操。 第二行有$n$个用空格隔开的非负整数，从左至右代表每只跳蚤的弹跳力。 第三行一个正整数$q$，表示下面有多少个操作。 下面一共$q$行，一共三种操作对原序列的操作：（假设此时一共$m$只跳蚤）

1. Q x y k: 询问从左至右第$x$只跳蚤到从左至右第$y$只跳蚤中，弹跳力第$k$小的跳蚤的弹跳力是多少。($1 \le x \le y \le m, 1 \le k \le y - x + 1$)
2. M x val: 将从左至右第x只跳蚤的弹跳力改为$val$。($1 \le x \le m$)
3. I x val: 在从左至右第$x$只跳蚤的前面插入一只弹跳力为$val$的跳蚤。即插入后从左至右第$x$只跳蚤是我刚插入的跳蚤。($1 \le x \le m + 1$)

为了体现在线操作，设$lastAns$为上一次查询的时候程序输出的结果，如果之前没有查询过，则$lastAns = 0$。

则输入的时候实际是：

• Q _x _y _k ——> 表示 Q _x^lastAns _y^lastAns _k^lastAns
• M _x _val ——> 表示 M _x^lastAns _val^lastAns
• I _x _val ——> 表示 I _x^lastAns _val^lastAns

简单来说就是操作中输入的整数都要异或上一次询问的结果进行解码。

(祝Pascal的同学早日转C++，就不提供pascal版的描述了。)

输出格式

输入输出样例

输入样例

10
10 5 8 28 0 19 2 31 1 22
30
I 6 9
M 1 11
I 8 17
M 1 31
M 6 26
Q 2 7 6
I 23 30
M 31 7
I 22 27
M 26 18
Q 26 17 31
I 5 2
I 18 13
Q 3 3 3
I 27 19
Q 23 23 30
Q 5 13 5
I 3 0
M 15 27
Q 0 28 13
Q 3 29 11
M 2 8
Q 12 5 7
I 30 19
M 11 19
Q 17 8 29
M 29 4
Q 3 0 12
I 7 18
M 29 27

输出样例

28
2
31
0
14
15
14
27
15
14

说明

$n \le 35000$；

插入个数 $\le 35000$，修改个数 $\le 70000$，查询个数 $\le 70000$ ,$0 \le$ 每时每刻的权值 $\le 70000$。

数据无梯度。

建议

每一个点时间开到3秒，否则根本过不去。