1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

const int MAXN = 100000,logn = 35;

const int L = -1e7,R=1e8+1e7;

struct SegTree{
  int siz[MAXN*logn],val[MAXN*logn],ls[MAXN*logn],rs[MAXN*logn];
  int root,cnt;
  #define mid ((l+r)>>1)
  void update(int &nown,int l,int r,int pos,int v){
    if(!nown) nown = ++cnt;
    if(l == r)
      val[nown] = v,siz[nown] = 0;
    else{
      if(pos <= mid)
        update(ls[nown],l,mid,pos,v);
      if(pos >= mid+1)
        update(rs[nown],mid+1,r,pos,v);
      siz[nown] = siz[ls[nown]] + siz[rs[nown]];
    }
  }
  void remove(int &nown,int l,int r,int pos){
    if(!nown) nown = ++cnt;
    if(l == r)
      siz[nown] = -1;
    else{
      if(pos <= mid)
        remove(ls[nown],l,mid,pos);
      if(pos >= mid+1)
        remove(rs[nown],mid+1,r,pos);
      siz[nown] = siz[ls[nown]] + siz[rs[nown]];
    }
  }
  int kth(int nown,int l,int r,int k,int &v){
    if(k > (r-l+1) + siz[nown]) return -1;
    if(l == r){
      v = val[nown];
      return l;
    }
    else{
      int sz = (mid-l+1) + siz[ls[nown]];
      if(k <= sz)
        return kth(ls[nown],l,mid,k,v);
      if(k > sz)
        return kth(rs[nown],mid+1,r,k-sz,v);
      return -1;
    }
  }
  int getsum(int nown,int l,int r,int ql,int qr){
    if(!nown) return 0;
    if(ql <= l && r <= qr){
      return siz[nown];
    }
    else{
      int ans = 0;
      if(ql <= mid)
        ans += getsum(ls[nown],l,mid,ql,qr);
      if(qr >= mid+1)
        ans += getsum(rs[nown],mid+1,r,ql,qr);
      return ans;
    }
  }
  void update(int pos,int v){update(root,L,R,pos,v);}
  void remove(int pos){remove(root,L,R,pos);}
  int kth(int k){int v=0,t = kth(root,L,R,k,v);return v!=0?v:t;}
  int getsum(int l,int r){return getsum(root,L,R,l,r);}
}T;

int n,m,nowl,nowr;

map<int,int> M;//在线段树中 x 出现的位置，没有则为没有动过

int getpos(int x){
  return M.count(x)?M[x]:x;
}

int push_top(int x){
  int pos = getpos(x),ans = (pos-nowl+1) + T.getsum(nowl,pos);
  T.remove(pos),T.update(--nowl,x);
  M[x] = nowl;
  return ans;
}

int push_bottom(int x){
  int pos = getpos(x),ans = (pos-nowl+1) + T.getsum(nowl,pos);
  T.remove(pos),T.update(++nowr,x);
  M[x] = nowr;
  return ans;
}

int change_id(int x,int y){
  int pos = getpos(x),ans = (pos-nowl+1) + T.getsum(nowl,pos);
  T.update(pos,y);
  M[y] = pos;
  return ans;
}

int query_id(int k){
  return T.kth((nowl-L)+k);
}

void init(){
  scanf("%d %d",&n,&m);
  nowl = 1,nowr = n;
}

void solve(){
  int lastans = 0;
  for(int i = 1;i<=m;i++){
    int op,x,y,k;
    scanf("%d",&op);
    if(op == 1){
      scanf("%d %d",&x,&y);
      x -= lastans,y -= lastans;
      lastans = change_id(x,y);
    }
    else if(op == 2){
      scanf("%d",&x);x -= lastans;
      lastans = push_top(x);
    }
    else if(op == 3){
      scanf("%d",&x);x -= lastans;
      lastans = push_bottom(x);
    }
    else if(op == 4){
      scanf("%d",&k);k -= lastans;
      lastans = query_id(k);
    }
    printf("%d\n",lastans);
  }
}

int main(){
  init();
  solve();
  return 0;
}