题目描述

\(\text{Sarah}\) 喜欢喝红茶，一天她要求 \(\text{Smart}\) 开卡车帮她运红茶过来。

红茶其实是编好号了的，从 \(0\) 开始一直到无穷……

一开始卡车上是没有红茶的，然后接下来到企鹅国的路上有 \(m\) 个时刻，每个时刻都会发生一种事情。

第一种事件，\(\text{Smart}\) 到了一个红茶店，买了一个编号为 \(x\) 的红茶（之前不会买过相同编号的红茶）。

第二种事件，一个目前在卡车上的编号为 \(x\) 的红茶飞出了卡车。

第三种事件，\(\text{Smart}\) 把目前不在卡车上的最早飞出去的红茶捡回了卡车上。

第四种事情，\(\text{Smart}\) 清点红茶，希望找到一个最小的编号，这种编号的红茶并不在卡车上。

格式

输入格式

第一行两个整数分别表示 \(m\) 和 \(czy\)。\(czy=1\) 表示进行强制在线，等于 \(0\) 则允许离线。

接下来 \(m\) 行，每行表示一个事件，首先会读入事件编号。

如果编号为 \(1\)，还要再读入一个数表示加入的红茶的编号。\(czy=1\) 时请把这个编号异或上一次的答案。

如果编号为 \(2\)，还要再读入一个数表示飞出去的红茶的编号。\(czy=1\) 时请把这个编号异或上一次的答案。

编号为 \(3\) 表示捡红茶。

编号为 \(4\) 表示询问。

初始时上一次的答案为 \(0\)。

输出格式

对于编号为 \(4\) 的事件输出一行表示答案。

样例1

样例输入1

10 0
1 0
1 1
1 2
1 3
2 1
4
3
4
1 4
4

样例输出1

1
4
5

限制

本题采取捆绑数据测试。

Task1(20分)：

\(M≤1000\)，红茶的编号在 \(1000\) 以内，\(czy=0\)；

Task2(20分)

\(m≤100000\)，红茶的编号在 \(100000\) 以内，\(czy=0\)；

Task3(20分)

\(m≤10000000\)，红茶的编号在 \(10000000\) 以内，\(czy=0\)；

Task4(40分)：

\(m≤10000000\)，红茶的编号在 \(\text{int}\) 范围以内，\(czy=1\)。

提示

由于数据范围很大，请采用快速读入方式读取输入数据。

inline int read(int &x)//快速读入
{char ch=getchar();
int f=1;x=0;
while (ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}

void write(int x)//快速输出
{if (!x) {putchar('0'); putchar('\n'); return;}
int k=0;
while (x){sta[++k]=x%10; x/=10;}
while (k) putchar('0'+sta[k--]);
putchar('\n');
}