终于用自己的方法水过去了。
本地测慢的一组要三四秒，一共要十几秒，BZOJ貌似一共只让跑6s，于是就还T着的。
一开始没看n<=1e8，想的直接splay+map（splay维护名次，map维护对应标号的节点所在位置）
然后写完看到n的范围 就傻了= =
百度了一下 splay里面的点要包含一段区间
想了半天 自己yy了一个做法：
一开始就一个点：[1,n+2]（虚拟节点什么的蛋疼死了，一会+1，一会-1）
于是需要[l,r]中的p点时，就拆成[l,p-1][p,p][p+1,r]，可是这样会不会影响树的形状？
分析一下，表示区间的点是不会有儿子的，所以我们可以很自然的把这样的点当成普通点看待。
然后又有一个问题，如何找到这个点在哪个区间里？
一开始想的建两个splay，另一个splay就是用来干这个的，觉得太麻烦就一直没写。
最后YY出用set来维护，用set<node(l,r,id)>来维护每个区间，每产生一个区间，就把他扔到set里，然后按r排序
不难发现，对于x，>=x的第一个r所在的区间一定包含它。然后找到split即可……
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<map>
#include<set>
using namespace std; const int Maxn=+;
inline int getint(){
int x=,f=;
char c=getchar();
for(;!isdigit(c)&&c!='-';c=getchar());
if(c=='-')f=;
for(;isdigit(c);c=getchar())x=x*+c-'';
return f?x:-x;
}
inline void getint(int&x){x=getint();}
struct node{
int l,r,id;
inline bool operator<(const node&rhs)const{return r<rhs.r;}
node(int l,int r,int id):l(l),r(r),id(id){}
};
int n,m,a;
map<int,int>pos;
set<node> Set;
typedef set<node>::iterator it;
typedef int pnode;
struct Splay{
int lp[Maxn],rp[Maxn],p[Maxn],l[Maxn],r[Maxn],sz[Maxn],v[Maxn],cnt,tot,root;
inline void update(int x){
if(lp[x]==rp[x])sz[x]=sz[l[x]]+sz[r[x]]+;
else sz[x]=rp[x]-lp[x]+;
}
inline void split(int x,int mid){// x is a node in Splay Tree and mid is a pointer but not a value
Set.erase(node(lp[x],rp[x],x));
int L=,R=;
if(lp[x]!=mid){
L=++tot;
l[x]=L;
p[L]=x;
lp[L]=lp[x];
rp[L]=mid-;
if(lp[L]==rp[L]){
v[L]=lp[x]-;
if(v[L]==n+)v[L]=;
if(v[L])pos[v[L]]=L;
}
else Set.insert(node(lp[L],rp[L],L));
}
if(rp[x]!=mid){
R=++tot;
r[x]=R;
p[R]=x;
lp[R]=mid+;
rp[R]=rp[x];
if(lp[R]==rp[R]){
v[R]=rp[x]-;
if(v[R]==n+)v[R]=;
if(v[R])pos[v[R]]=R;
}
else Set.insert(node(lp[R],rp[R],R));
}
v[x]=mid-;
if(v[x]==n+)v[x]=;
if(v[x])pos[v[x]]=x;
rp[x]=lp[x]=mid;
if(L)update(L);
if(R)update(R);
update(x);
}
inline int find(int x){// x is stand for val
int t=pos[x];
if(t)return t;
it p=Set.lower_bound(node(,x+,));
t=p->id;
split(t,x+);
return t;
}
inline void zig(int x){
int y=p[x],z=p[y],w=r[x];
l[y]=w;r[x]=y;
if(l[z]==y)l[z]=x;
if(r[z]==y)r[z]=x;
p[x]=z;p[y]=x;if(w)p[w]=y;
update(y);update(x);
}
inline void zag(int x){
int y=p[x],z=p[y],w=l[x];
r[y]=w;l[x]=y;
if(l[z]==y)l[z]=x;
if(r[z]==y)r[z]=x;
p[x]=z;p[y]=x;if(w)p[w]=y;
update(y);update(x);
}
inline void rotate(int x){
if(l[p[x]]==x)zig(x);else zag(x);
}
inline void splay(int x,int FA){
for(;p[x]!=FA;){
int y=p[x],z=p[y];
if(z!=FA){
if( (l[y]==x)^(l[z]==y) )rotate(x);else rotate(y);
}
rotate(x);
}
if(!FA)root=x;
}
inline void init(){
cnt=tot=sz[]=;
root=++tot=;
lp[root]=,rp[root]=n+;
Set.insert(node(,n+,root));
update(root);
}
int kth(int o,int k){
if(rp[o]!=lp[o]){
split(o,lp[o]+k-);
return o;
}
int s=sz[l[o]];
if(s+==k)return o;
if(s+<k)return kth(r[o],k-s-);
return kth(l[o],k);
}
inline int deal(){
if(m==)
m=;
int x,y,opt;
getint(opt);
if(opt==){
getint(x),getint(y);
x-=a,y-=a;
int o=find(x);
v[o]=y;
pos[x]=;
pos[y]=o;
splay(o,);
return a=sz[l[o]];
}
else if(opt==||opt==){
getint(x);x-=a;
x=find(x);
splay(x,);
int rk=sz[l[x]];
if(rk==n&&opt==)return a=rk;
if(rk==&&opt==)return a=rk;
int lt=kth(root,rk- +),rt=kth(root,rk+ +);//for the static 1
splay(lt,);
splay(rt,lt);
l[rt]=;
update(rt);
update(lt);
int fst,snd;
if(opt==)fst=kth(root,),snd=kth(root,);
else fst=kth(root,n),snd=kth(root,n+);//for 1 has been killed
splay(fst,);
splay(snd,fst);
l[snd]=x;
p[x]=snd;
update(snd);
update(fst);
return a=rk;
}
else {
getint(x);x-=a;
return a=v[kth(root,x+)];
}
}
}sp;
int main(){
freopen("onlinejudge.in","r",stdin);
freopen("onlinejudge.out","w",stdout);
scanf("%d%d",&n,&m);
sp.init();
for(;m--;)printf("%d\n",sp.deal());
return ;
}