C++ :

/*
线段树套权值线段树
外层权值线段树维护每个数字出现的次数，内层维护在每个区间出现次数，然后外层二分查找，内层query区间和
边运行边建树，防止MLE
*/
#include<cstdio>
using namespace std;
int n,m,n1,n2,n3,n4,k,num,room,tot1,tot2;
inline void read(int&a){
  char ch;while(!((ch=getchar())>='0')&&(ch<='9'));
  a=ch-'0';while(((ch=getchar())>='0')&&(ch<='9'))a*=10,a+=ch-'0';
}
struct node1{int l,r,t;}tree1[10000000];
struct node2{int l,r,tmp;long long f;}tree2[10000000];
void cover(int p,int l,int r){
  int mid=(l+r)>>1;
  if((l>=n2)&&(r<=n3)){
    ++tree2[p].tmp;
    return;
  }
  if(tree2[p].tmp){
    if(!tree2[p].l)tree2[p].l=++tot2;
    if(!tree2[p].r)tree2[p].r=++tot2;
  }
  if(n3<=mid){
    if(!tree2[p].l)tree2[p].l=++tot2;
    if(tree2[p].tmp){
      tree2[tree2[p].l].tmp+=tree2[p].tmp;
      tree2[tree2[p].r].tmp+=tree2[p].tmp;
      tree2[p].tmp=0;
    }
    cover(tree2[p].l,l,mid);
  }else{
    if(n2>mid){
      if(!tree2[p].r)tree2[p].r=++tot2;
      if(tree2[p].tmp){
        tree2[tree2[p].r].tmp+=tree2[p].tmp;
        tree2[tree2[p].l].tmp+=tree2[p].tmp;
        tree2[p].tmp=0;
      }
      cover(tree2[p].r,mid+1,r);
    }else{
      if(!tree2[p].l)tree2[p].l=++tot2;
      if(!tree2[p].r)tree2[p].r=++tot2;
      if(tree2[p].tmp){
        tree2[tree2[p].l].tmp+=tree2[p].tmp;
        tree2[tree2[p].r].tmp+=tree2[p].tmp;
        tree2[p].tmp=0;
      }
      cover(tree2[p].l,l,mid);
      cover(tree2[p].r,mid+1,r);
    }
  }
  tree2[p].f=0;
  if(tree2[p].l)tree2[p].f+=tree2[tree2[p].l].tmp*(r-mid)+tree2[tree2[p].l].f;
  if(tree2[p].r)tree2[p].f+=tree2[tree2[p].r].tmp*(r-mid)+tree2[tree2[p].r].f;
}
void build(int p,int l,int r){
  if(!tree1[p].t)tree1[p].t=++tot2;
  cover(tree1[p].t,1,room);
  if(l==r)return;
  int mid=(l+r)>>1;
  if(n4<=mid){
    if(!tree1[p].l)tree1[p].l=++tot1;
    build(tree1[p].l,l,mid);
  }else{
    if(!tree1[p].r)tree1[p].r=++tot1;
    build(tree1[p].r,mid+1,r);
  }
}
long long find(int p,int l,int r){
  int t1,t2;
  if((!tree2[p].l)&&(!tree2[p].r)){
    t1=n2>l?n2:l;t2=n3<r?n3:r;
    return tree2[p].tmp*(t2-t1+1);
  }
  if((l>=n2)&&(r<=n3))return tree2[p].tmp*(r-l+1)+tree2[p].f;
  long long tmp=0;
  int mid=(l+r)>>1;
  if(n3<=mid){
    if(tree2[p].l)tmp+=find(tree2[p].l,l,mid);
  }else{
    if(n2>mid){
      if(tree2[p].r)tmp+=find(tree2[p].r,mid+1,r);
    }else{
      if(tree2[p].l)tmp+=find(tree2[p].l,l,mid);
      if(tree2[p].r)tmp+=find(tree2[p].r,mid+1,r);
    }
  }
  t1=n2>l?n2:l;t2=n3<r?n3:r;
  return tmp+tree2[p].tmp*(t2-t1+1);
}
int ask(int p,int l,int r){
  if(l==r)return l;
  int mid=(l+r)>>1,tmp;
  if(tree1[p].r){
    tmp=find(tree1[tree1[p].r].t,1,room);
    if(tmp>=n4)return ask(tree1[p].r,mid+1,r);else n4-=tmp;
  }
  return ask(tree1[p].l,l,mid);
}
int main(){
  read(n);read(m);
  num=room=tot1=1;
  while(num<=n+1)num<<=1;
  while(room<=n)room<<=1;
  while(m--){
    read(n1);read(n2);read(n3);read(n4);
    if(n1==1)build(1,0,num-1);else printf("%d\n",ask(1,0,num-1));
  }
  return 0;
}