#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define ll long long
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 1000005
#define N 10000005
#define inf 0x3f3f3f3f

void op1(int x,int y);
void op2(int k);

// dep = 10~0 , dep = 0 is leaf 
int pw[114],num;
int sz[N],v0[N],rt,cnt=1000000; 
bool col[N];
vi ch[N],nd0[N],nd1[N];

inline void upsiz(int u){
	sz[u]=0;
	for(auto v:ch[u])sz[u]+=sz[v];
}
void dfs(int u,int d,int tp,int fg){
	if(!d){
		if(fg) nd1[tp].pb(u);
		else nd0[tp].pb(u);
	}
	for(auto v:ch[u])dfs(v,d-1,tp,fg); 
}
void color(int u,int d){
	v0[u]=++cnt,++cnt;
	col[cnt-1]=col[cnt]=col[u];
	int now=0,flag=0;
	for(int i=0;i<ch[u].size();++i){
		int v=ch[u][i];
		now+=sz[v];
		dfs(v,d-1,u,col[v]=flag);
		if(now>=pw[d-1])flag=1;
	}
}
void split(int u,int f,int d){
	col[v0[u]]=col[v0[u]+1]=col[u];
	for(auto v:ch[u]) ch[v0[u]+col[v]].pb(v);
	ch[u].clear(),ch[u].shrink_to_fit();
	vi nch;
	for(auto v:ch[f]){
		if(v==u) nch.pb(v0[u]),nch.pb(v0[u]+1);
		else nch.pb(v);
	}
	ch[f]=nch;
	upsiz(v0[u]),upsiz(v0[u]+1);
}
void ins(int&u,int pa,int d,int k)
{
	if(!u) u=++cnt;
	if(!d) exit(233);
	
	op1(u,num),++sz[u];
	
	if(d==1){
		vi nch;
		For(i,0,k-1)nch.pb(ch[u][i]);
		nch.pb(num);
		For(i,k,(int)ch[u].size()-1)nch.pb(ch[u][i]);
		ch[u]=nch;
		if(ch[u].size()==4){
			v0[u]=++cnt,++cnt;
			sz[cnt-1]=sz[cnt]=2;
			col[cnt-1]=col[cnt]=col[u];
			For(i,0,3){
				int v=ch[u][i];
				col[v]=(i>1);
				op1(v0[u]+col[v],v);
			}
			split(u,pa,d);
		}
		return;
	}
	
	if(!ch[u].size()) ch[u].pb(++cnt);
	if(sz[u]==3*pw[d-1]+1)
		color(u,d);
	
	for(auto v:ch[u]){
		if(k<=sz[v]){
			ins(v,u,d-1,k);
			if(sz[u]>3*pw[d-1]) op1(col[v]+v0[u],num);
			break;
		}
		k-=sz[v];
	}
	if(sz[u]>3*pw[d-1]){
		int s=3;
		while(s&&nd0[u].size()) op1(v0[u],nd0[u].back()),nd0[u].pop_back(),--s;
		while(s&&nd1[u].size()) op1(v0[u]+1,nd1[u].back()),nd1[u].pop_back(),--s;
	}
	if(sz[u]==pw[d]) split(u,pa,d);
}
void ask(int u,int l,int r)
{
	if(l>r||r<=0||l>sz[u])return;
	if(l==1&&r==sz[u])return op2(u);
	for(auto v:ch[u]){
		ask(v,max(l,1),min(r,sz[v]));
		l-=sz[v],r-=sz[v];
		if(r<=0)break;
	}
}

void init(){
	pw[0]=1; sz[0]=1;
	For(i,1,11)pw[i]=pw[i-1]<<2;
}
void solve(int x,int l,int r)
{
	if(!num)init();
	++num; op1(num,num); sz[num]=1;
	ins(rt,0,10,x-1);
	ask(rt,l,r);
}

//signed main(){
//	solve(1,1,1);
//	return 0;
//}