1 #include<cstdio> 2 #include<algorithm> 3 #define mid ((l+r)>>1) 4 using namespace std; 5 long long cas,a,b,c,k,l,r,n,m,sz; 6 int root[200005]; 7 int ls[10000005],rs[10000005],sum[10000005],lazy[10000005]; 8 void pushdown(int k,int l,int r) 9 {10     if(!lazy[k]||l==r)return;11     if(!ls[k])ls[k]=++sz;12     if(!rs[k])rs[k]=++sz;13     lazy[ls[k]]+=lazy[k];lazy[rs[k]]+=lazy[k];14     sum[ls[k]]+=(mid-l+1)*lazy[k];15     sum[rs[k]]+=(r-mid)*lazy[k];16     lazy[k]=0;17 }18 void add(int k,int l,int r,int a,int b)19 {20     if(l==a&&r==b)21     {22         sum[k]+=r-l+1;23         lazy[k]++;24         return;25     }26     pushdown(k,l,r);27     if(a<=mid)ls[k]=ls[k]?ls[k]:++sz,add(ls[k],l,mid,a,min(b,mid));28     if(b>mid)rs[k]=rs[k]?rs[k]:++sz,add(rs[k],mid+1,r,max(mid+1,a),b);29     sum[k]=sum[ls[k]]+sum[rs[k]];30 }31 long long que(int k,int l,int r,int a,int b)32 {33     if(!k)return 0;34     if(l==a&&r==b)return sum[k];35     pushdown(k,l,r);36     if(b<=mid)return que(ls[k],l,mid,a,b);37     else if(a>mid)return que(rs[k],mid+1,r,a,b);38     else return que(ls[k],l,mid,a,mid)+que(rs[k],mid+1,r,mid+1,b);39 }40 int solve()41 {42     int l=1,r=2*n,k=1;43     while(l!=r)44     {45         long long t=que(root[k<<1|1],1,n,a,b);46         if(c<=t)l=mid+1,k=k<<1|1;47         else r=mid,k=k<<1,c-=t;48     }49     return l;50 }51 int main()52 {53     for(scanf("%d%d",&n,&m);m;m--)54     {55         scanf("%d%d%d%d",&cas,&a,&b,&c);56         if(cas==1)57             for(k=1,l=1,r=2*n,c+=n;l!=r;root[k]=root[k]?root[k]:++sz,add(root[k],1,n,a,b))58                 if(c<=mid)r=mid,k=k<<1;59                 else l=mid+1,k=k<<1|1;60         else printf("%d\n",solve()-n);61     }62     return 0;63 }