我们想到用平衡树维护这个东西，但常见的平衡树都是均摊和期望的，所以我们考虑固定每一层的集合大小和深度，便于分析复杂度。

我们构造一个 Leafy Tree，第 $i$ 层的节点对应的集合大小为 $[4^{i-1},4^i)$，叶子（第 $0$ 层）节点大小为 $1$。

单次插入的操作次数就是深度，也就是 $11$ 的样子。

一个节点最多有 $15$ 个儿子，所以查询的操作次数大概在深度乘二倍的儿子数左右，常数很小，应该能控制在 $256$ 次内。

现在的问题就是插入后如果一个节点集合大小超过了上界，如何处理。

考虑分裂，但是分裂后的集合需要重新维护，我们如果暴力插入的话，均摊复杂度显然是正确的，但我们要保证 Worst Case，所以不能暴力。

我们认为一个集合大小等于 $3\times 4^{i-1}$ 的节点是即将分裂的，这样的节点再进行 $4^{i-1}$ 次插入就会分裂，我们维护它分裂出的两个集合，每进行一次插入就向分裂后的集合进行四次插入，这样当它分裂时，我们正好维护出了它分裂出的两个集合，这里有一点小细节，就是我们要保证分裂出的集合大小在 $[4^{i-1},4^i)$，并且要恰好把儿子分成两部分。

void op1(int x,int y);
void op2(int k);
struct node{
	int fa,sz,dg1,dg2,dg,sons,son[16];
}tr[4100000];
int rt,cnt;
int que(int p,int x,int dp){
	if(dp==-1) return tr[x].dg;
	for(int i=0,pk=0;i<tr[x].sons;i++){
		int pl,pr;
		pl=pk+1,pr=pk+tr[tr[x].son[i]].sz;
		if(pl<=p&&p<=pr) return que(p-pk,tr[x].son[i],dp-1);
		pk=pr;
	}
	return 0;
}
void insert(int p,int val,int x,int dp){
	op1(x,val);
	if(dp==0){
		for(int i=tr[x].sons-1;i>=p;i--)tr[x].son[i+1]=tr[x].son[i];
		++tr[x].sons;
		tr[x].son[p]=++cnt;
		tr[cnt].dg=val;
		op1(cnt,val);
		tr[cnt].fa=x,tr[cnt].sz=1;
	}else{
		for(int i=0,k=p;i<tr[x].sons;i++){
			if(k<=tr[tr[x].son[i]].sz){insert(k,val,tr[x].son[i],dp-1);break;}
			k-=tr[tr[x].son[i]].sz;
		}
	}
	++tr[x].sz;
	if(tr[x].sz<=3*(1<<(dp*2)))return;
	if(!tr[x].dg1){
		tr[x].dg1=++cnt,tr[x].dg2=++cnt;
		for(int i=0,d=0;i<tr[x].sons;i++){
			d+=tr[tr[x].son[i]].sz;
			if(d>(1<<(dp*2))){
				tr[x].dg=d;
				break;
			}
		}
		op1(tr[x].dg1,que(1,x,dp));
		op1(tr[x].dg1,que(2,x,dp));
		op1(tr[x].dg2,que(tr[x].sz,x,dp));
		op1(tr[x].dg2,que(tr[x].sz-1,x,dp));
		tr[tr[x].dg1].sz=2,tr[tr[x].dg2].sz=tr[x].sz-2;
	}else{
		int cct;
		if(p<=tr[x].dg){
			++tr[x].dg;
			if(p<=tr[tr[x].dg1].sz) ++tr[tr[x].dg1].sz,op1(tr[x].dg1,val),cct=3;else cct=4;
			++tr[tr[x].dg2].sz;
		}else{
			if(p>tr[tr[x].dg2].sz) op1(tr[x].dg2,val),cct=3;else cct=4,++tr[tr[x].dg2].sz;
		}
		while(cct&&tr[tr[x].dg1].sz<tr[x].dg) --cct,op1(tr[x].dg1,que(++tr[tr[x].dg1].sz,x,dp));
		while(cct&&tr[tr[x].dg2].sz>tr[x].dg) --cct,op1(tr[x].dg2,que(tr[tr[x].dg2].sz--,x,dp));
	}
	if(tr[x].sz==(1<<(dp*2+2))){
		int u=tr[x].dg1,v=tr[x].dg2;
		int fa=tr[u].fa=tr[v].fa=tr[x].fa;
		tr[v].sz=tr[x].sz-tr[u].sz;
		for(int i=0,d=0;i<tr[x].sons;i++){
			d+=tr[tr[x].son[i]].sz;
			if(d<=tr[u].sz) tr[tr[u].son[tr[u].sons++]=tr[x].son[i]].fa=u;
			else tr[tr[v].son[tr[v].sons++]=tr[x].son[i]].fa=v;
		}
		for(int i=0;i<tr[fa].sons;i++)if(tr[fa].son[i]==x){
			for(int j=tr[fa].sons-1;j>i;j--) tr[fa].son[j+1]=tr[fa].son[j];
			++tr[fa].sons;
			tr[fa].son[i]=u,tr[fa].son[i+1]=v;
			break;
		}
	}
}
void query(int l,int r,int x){
	if(l==1&&r==tr[x].sz) return op2(x);
	for(int i=0,pk=0;i<tr[x].sons;i++){
		int pl,pr;
		pl=pk+1,pr=pk+tr[tr[x].son[i]].sz;
		if(l<=pl&&pr<=r) query(pl-pk,pr-pk,tr[x].son[i]);
		else if(pl<=l&&r<=pr) query(l-pk,r-pk,tr[x].son[i]);
		else if(pl<=l&&l<=pr&&pr<=r) query(l-pk,pr-pk,tr[x].son[i]);
		else if(l<=pl&&pl<=r&&r<=pr) query(pl-pk,r-pk,tr[x].son[i]);
		pk=pr;
	}
}
int i;
void solve(int x,int l,int r){
	if(!rt){
		rt=++cnt;
		for(int i=0;i<9;i++){
			tr[++cnt].son[0]=rt;
			tr[cnt].sons=1;
			tr[cnt].sz=0;
			tr[rt].fa=cnt;
			rt=cnt;
		}
	}
	insert(x-1,++i,rt,9);
	query(l,r,rt);
}