好像整体二分跑得飞快，不过蒟蒻是来练树套树的。才不是我不会任何离线算法
操作涉及区间插入、区间查询k小值。先想到了权值线段树套平衡树，平衡树存储位置。
查询时（假设查询区间 $[l,r]$ 的第k名）从权值线段树根节点出发，查询右儿子平衡树的$r$的排名-（$l-1$）的排名，也就是右边区间中在区间 $[l,r]$的数的个数，比$k$小，就让$k$减去它，跳到左儿子上；反之跳到右儿子上。（比较像主席树区间$k$大值）
插入暴力将每个位置挨个插到平衡树中。
复杂度 $O(nlog^{2}n+len*log^{2}n)$ $\text{（len为总插入数字的个数）}$
$T$了$10$个点。$len$非常大。瓶颈就在于插入。一个个插入确实太慢了，有没有什么能快速把一段连续区间加进去？
线段树可以。权值线段树里套一个维护位置的线段树。插入直接区间加 $1$，查询区间求和，时间都是$logn$的。为了保证空间，还要动态开点。
时间复杂度：每次插入查询都要访问权值线段树的$logn$个节点，每个节点要访问内部的线段树的$logn$个节点。总复杂度$O(nlog^{2}n)$。
空间复杂度：每次插入都要访问权值线段树的$logn$个节点，每个节点内部的线段树最多会新开$logn$个节点，总复杂度$O(nlog^{2}n)$。
不过毕竟树套树常数大，容易 $T$ 。搞个标记永久化能优化不少。不过蒟蒻并不会卡常，程序自带大常数（比如AC自动机永远跑不进 $9000ms$），标记永久化还是 $T$ 了一个点。加了$fread$、快输才能不开$O2$过。
上代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 50005
#define inf 0x3f3f3f
#define pn putchar('\n')
#define px(x) putchar(x)
#define ps putchar(' ')
#define pd puts("======================")
#define pj puts("++++++++++++++++++++++")
#define getchar() (*head++)
using namespace std;
char buf[1<<23],*head=buf;//fread优化
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
template<typename T>
inline T read(){
T x=0;
int y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}//快读
void put(int x){
if(x<0)px('-')，x=-x;
if(x>9)put(x/10);
px(x%10+48);
}//快输
int n;
#define ls(x) ls[x]
#define rs(x) rs[x]
struct Position_Segment_Tree{
long long dat[maxn*400];
int tag[maxn*400],ls[maxn*400],rs[maxn*400],cnt;
void add(int L,int R,int l,int r,int &node){
if(!node)node=++cnt;//动态开点
dat[node]+=(long long)(min(R,r)-max(L,l)+1);//标记永久化
if(L<=l&&R>=r){
++tag[node];
return;
}
int mid=l+r>>1;
if(L<=mid)add(L,R,l,mid,ls(node));
if(R>mid)add(L,R,mid+1,r,rs(node));
}
long long ask(int L,int R,int l,int r,int node,long long t=0){
if(!node)return (long long)(min(R,r)-max(L,l)+1)*t;
if(L<=l&&R>=r)return dat[node]+1ll*(min(R,r)-max(L,l)+1)*t;
int mid=l+r>>1;
long long ans=0;
if(L<=mid)ans=ask(L,R,l,mid,ls(node),t+tag[node]);
if(R>mid)ans+=ask(L,R,mid+1,r,rs(node),t+tag[node]);
return ans;
}
}pst;
#undef ls
#undef rs
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
struct Data_Segment_Tree{
int root[maxn<<3];
void insert(int poi,int L,int R){
int l=-n,r=n,node=1;
while(1){
pst.add(L,R,1,n,root[node]);
if(l==r)return;
int mid=l+r>>1;
if(poi<=mid)node=ls(node),r=mid;
else node=rs(node),l=mid+1;
}
}//为了卡常把递归改成了非递归的。不过好像没什么效果。。。
void ask(int L,int R,long long k){
int l=-n,r=n,node=1;
while(l<r){
int mid=l+r>>1;
long long sum=pst.ask(L,R,1,n,root[rs(node)]);
if(sum>=k)node=rs(node),l=mid+1;
else k-=sum,node=ls(node),r=mid;
}
put(l),pn;
}
}dst;
int main(){
fread(buf,1,1<<23,stdin);
n=read();
int m=read();
while(m--){
int s=read(),l=read(),r=read();
if(s==1){
int d=read();
dst.insert(d,l,r);
}
else {
long long k=read<long long>();
dst.ask(l,r,k);
}
}
}
