# 1. 题目

BZOJ – 3110：传送门=￣ω￣=

LUOGU – 3332：传送门=￣ω￣=

# 2. 题解

#include <bits/stdc++.h>
#define NS (50005)
#define MS (50005)
#define LS(a) (a<<1)
#define RS(a) (a<<1|1)
using namespace std;
typedef long long LL;
template<typename _Tp>inline void IN(_Tp&dig)
{
char c;bool flag=0;dig=0;
while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
if(flag)dig=-dig;
}
struct Query{int l,r,id,type;LL k;}Q[MS],Q1[MS],Q2[MS];
struct N{int l,r,tag;LL d;}e[NS<<2];
int n,m,cnt,qcnt,ans[MS];
void pdown(int a)
{
if(e[a].tag)
{
e[LS(a)].d+=(e[LS(a)].r-e[LS(a)].l+1)*e[a].tag,e[LS(a)].tag+=e[a].tag;
e[RS(a)].d+=(e[RS(a)].r-e[RS(a)].l+1)*e[a].tag,e[RS(a)].tag+=e[a].tag;
e[a].tag=0;
}
}
void pup(int a){e[a].d=e[LS(a)].d+e[RS(a)].d;}
void build(int l,int r,int a)
{
e[a].l=l,e[a].r=r;
if(l==r)return;
int mid=(l+r)>>1;
build(l,mid,LS(a)),build(mid+1,r,RS(a));
}
void update(int l,int r,LL d,int a)
{
if(l<=e[a].l&&e[a].r<=r){e[a].d+=(e[a].r-e[a].l+1)*d,e[a].tag+=d;return;}
pdown(a);
if(l<=e[LS(a)].r)update(l,r,d,LS(a));
if(r>=e[RS(a)].l)update(l,r,d,RS(a));
pup(a);
}
LL query(int l,int r,int a)
{
if(l<=e[a].l&&e[a].r<=r)return e[a].d;
pdown(a);
LL tot=0;
if(l<=e[LS(a)].r)tot+=query(l,r,LS(a));
if(r>=e[RS(a)].l)tot+=query(l,r,RS(a));
}
void binary(int QL,int QR,int l,int r)
{
if(QL>QR)return;
if(l==r){for(int i=QL;i<=QR;i++)if(Q[i].type)ans[Q[i].id]=l;return;}
int mid=(l+r)>>1,x1=0,x2=0;
for(int i=QL;i<=QR;i++)
if(Q[i].type)
{
LL tmp=query(Q[i].l,Q[i].r,1);
if(Q[i].k<=tmp)Q1[++x1]=Q[i];
else Q2[++x2]=Q[i],Q2[x2].k-=tmp;
}
else
{
if(Q[i].k<=mid)update(Q[i].l,Q[i].r,1,1),Q1[++x1]=Q[i];
else Q2[++x2]=Q[i];
}
for(int i=1;i<=x1;i++)if(!Q1[i].type)update(Q1[i].l,Q1[i].r,-1,1);
for(int i=1;i<=x1;i++)Q[QL+i-1]=Q1[i];
for(int i=1;i<=x2;i++)Q[QL+x1+i-1]=Q2[i];
binary(QL,QL+x1-1,l,mid),binary(QL+x1,QR,mid+1,r);
}
int main()
{
IN(n),IN(m),build(1,n,1);
int opt,a,b;LL c;
for(int i=1;i<=m;i++)
if(IN(opt),IN(a),IN(b),IN(c),opt==1)Q[++cnt]=(Query){a,b,0,0,-c};
else Q[++cnt]=(Query){a,b,++qcnt,1,c};
binary(1,cnt,-NS,NS);
for(int i=1;i<=qcnt;i++)printf("%d\n",-ans[i]);
return 0;
}