#include<iostream>
#include<algorithm>
#include<cstdio>
#include<map>
#define MAXN 1000010
using namespace std;
map<int,int> pos;
int n,m;
int size=0,root=0;
struct Splay{
int f,s,son[2];
int l,r;
}a[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
return date*w;
}
inline void pushup(int rt){
if(!rt)return;
a[rt].s=a[a[rt].son[0]].s+a[a[rt].son[1]].s+a[rt].r-a[rt].l+1;
}
inline void turn(int rt,int k){
int x=a[rt].f,y=a[x].f;
a[x].son[k^1]=a[rt].son[k];
if(a[rt].son[k])a[a[rt].son[k]].f=x;
a[rt].f=y;
if(y)a[y].son[a[y].son[1]==x]=rt;
a[x].f=rt;
a[rt].son[k]=x;
pushup(x);pushup(rt);
}
void splay(int rt,int ancestry){
while(a[rt].f!=ancestry){
int x=a[rt].f,y=a[x].f;
if(y==ancestry)turn(rt,a[x].son[0]==rt);
else{
int k=a[y].son[0]==x?1:0;
if(a[x].son[k]==rt){turn(rt,k^1);turn(rt,k);}
else{turn(x,k);turn(rt,k);}
}
}
if(ancestry==0)root=rt;
}
int newnode(int l,int r){
int rt=++size;
a[rt].son[0]=a[rt].son[1]=a[rt].f=0;
a[rt].l=l;a[rt].r=r;
a[rt].s=r-l+1;
return rt;
}
inline void buildtree(){
root=newnode(1,n);
a[root].s=n;
pos[n]=root;
}
int kth(int rt,int k){
if(k>a[rt].s)return 0;
while(k){
int s=a[a[rt].son[0]].s+a[rt].r-a[rt].l+1;
if(a[a[rt].son[0]].s<k&&k<=s){
k-=a[a[rt].son[0]].s;
break;
}
if(s<k){
k-=s;
rt=a[rt].son[1];
}
else rt=a[rt].son[0];
}
return a[rt].l+k-1;
}
void remove(int rt){
int front=a[rt].son[0],next=a[rt].son[1];
while(a[front].son[1])front=a[front].son[1];
while(a[next].son[0])next=a[next].son[0];
if(!front&&!next)root=0;
else if(!front){
splay(next,root);
root=next;
a[root].f=0;
a[rt].son[0]=a[rt].son[1]=0;
a[rt].s=1;
}
else if(!next){
splay(front,root);
root=front;
a[root].f=0;
a[rt].son[0]=a[rt].son[1]=0;
a[rt].s=1;
}
else{
splay(front,0);splay(next,front);
a[next].son[0]=a[rt].f=0;
a[rt].s=1;
pushup(next);pushup(front);
}
}
void split(int x,int id){
if(a[x].l==a[x].r)return;
int l=a[x].l,r=a[x].r,lson,rson;
if(l==id){
rson=newnode(l+1,r);
pos[r]=rson;pos[id]=x;
a[rson].son[1]=a[x].son[1];
a[a[rson].son[1]].f=rson;
a[x].son[1]=rson;a[rson].f=x;
a[x].r=l;
pushup(rson);pushup(x);
}
else if(r==id){
lson=newnode(l,r-1);
pos[r-1]=lson;pos[id]=x;
a[lson].son[0]=a[x].son[0];
a[a[lson].son[0]].f=lson;
a[x].son[0]=lson;a[lson].f=x;
a[x].l=r;
pushup(lson);pushup(x);
}
else{
lson=newnode(l,id-1);rson=newnode(id+1,r);
pos[id]=x;pos[id-1]=lson;pos[r]=rson;
a[lson].son[0]=a[x].son[0];a[rson].son[1]=a[x].son[1];
a[a[lson].son[0]].f=lson;a[a[rson].son[1]].f=rson;
a[x].son[0]=lson;a[x].son[1]=rson;a[lson].f=a[rson].f=x;
a[x].l=a[x].r=id;
pushup(lson);pushup(rson);pushup(x);
}
splay(x,0);
}
inline int change(int x,int y){
int k=pos.lower_bound(x)->second,s;
split(k,x);
splay(k,0);
s=a[k].s-a[a[k].son[1]].s;
a[k].l=a[k].r=y;
pos[y]=k;
return s;
}
inline void push_head(int rt){
if(!root){root=rt;return;}
int fa=root;
while(a[fa].son[0]){
a[fa].s++;
fa=a[fa].son[0];
}
a[fa].s++;
a[fa].son[0]=rt;
a[rt].f=fa;
splay(rt,0);
}
inline void push_last(int rt){
if(!root){root=rt;return;}
int fa=root;
while(a[fa].son[1]){
a[fa].s++;
fa=a[fa].son[1];
}
a[fa].s++;
a[fa].son[1]=rt;
a[rt].f=fa;
splay(rt,0);
}
inline int make_head(int x){
int k=pos.lower_bound(x)->second,s;
split(k,x);
splay(k,0);
s=a[k].s-a[a[k].son[1]].s;
remove(k);
push_head(k);
return s;
}
inline int make_last(int x){
int k=pos.lower_bound(x)->second,s;
split(k,x);
splay(k,0);
s=a[k].s-a[a[k].son[1]].s;
remove(k);
push_last(k);
return s;
}
void work(){
int f,x,y,last=0;
while(m--){
f=read();x=read()-last;
switch(f){
case 1:{
y=read()-last;
last=change(x,y);
printf("%d\n",last);
break;
}
case 2:{
last=make_head(x);
printf("%d\n",last);
break;
}
case 3:{
last=make_last(x);
printf("%d\n",last);
break;
}
case 4:{
last=kth(root,x);
printf("%d\n",last);
break;
}
}
}
}
void init(){
n=read();m=read();
buildtree();
}
int main(){
init();
work();
return 0;
}
