codechef XRQRS

时间限制:10s      空间限制:128MB

题目描述

给定一个初始时为空的整数序列(元素由1开始标号)以及一些询问:
类型1:在数组后面就加入数字x。
类型2:在区间L…R中找到y,最大化(x xor y)。
类型3:删除数组最后K个元素。
类型4:在区间L…R中,统计小于等于x的元素个数。
类型5:在区间L…R中,找到第k小的数。


输入格式

输入数据第一行为一个整数q,表示询问个数,接下来q行,每行一条询问 对应题目描述。
类型1的询问格式为“1 x”。
类型2的询问格式为“2 L R x”。
类型3的询问格式为“3 k”。
类型4的询问格式为“4 L R x”。
类型5的询问格式为“5 L R k”。


输出格式

对于每个2、4、5询问输出一行对应答案


样例输入

10
1 8
5 1 1 1
1 2
2 2 2 7
2 2 2 7
1 1
4 2 2 2
2 1 2 3
4 1 3 5
1 6

样例输出

8
2
2
1
8
2

提示

令N表示每次询问前数组中元素的个数
1<=L<=R<=N
1<=x<=500,000
对于第三类询问 1<=k<=N       
对于第五类询问 k<=R-L+1 
1<=N<=500,000


题目来源

没有写明来源