#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
typedef vector<int>vi;
void op1(int x,int y);
void op2(int k);
int T,pw[15],sz[N],rt,cnt=1e6,id[N];
bool co[N];
vi s[N],s0[N],s1[N];
void init(){
	pw[0]=1;
	for(int i=1;i<=11;++i)pw[i]=pw[i-1]*4;
}
void query(int x,int l,int r){
	if(l>r||r<1||l>sz[x])return;
	if(l==1&&r==sz[x])return op2(x);
	for(auto v:s[x]){
		query(v,max(l,1),min(r,sz[v]));
		l-=sz[v],r-=sz[v];
	}
}
void dfs(int x,int y,int d,bool fg){
	if(!d){
		if(fg)s1[y].push_back(x);
		else s0[y].push_back(x);
	}
	for(auto v:s[x])dfs(v,y,d-1,fg);
}
void upd(int x){
	sz[x]=0;
	for(auto v:s[x])sz[x]+=sz[v];
}
void color(int x,int d){
	id[x]=++cnt,++cnt;
	co[cnt]=co[cnt-1]=co[x];
	int S=0;
	bool fg=false;
	for(auto v:s[x]){
		S+=sz[v];
		dfs(v,x,d-1,co[v]=fg);
		if(S>=pw[d-1])fg=true;
	}
}
void split(int x,int y,int d){
	int u=id[x];
	co[u]=co[u+1]=co[x];
	for(auto v:s[x])s[u+co[v]].push_back(v);
	s[x].clear(),s[x].shrink_to_fit();
	vi tmp;
	for(auto v:s[y]){
		if(v==x)tmp.push_back(u),tmp.push_back(u+1);
		else tmp.push_back(v);
	}
	s[y]=tmp;
	upd(u),upd(u+1);
}
void ins(int &x,int y,int d,int k){
	if(!x)x=++cnt;
	op1(x,T),++sz[x];
	if(d==1){
		vi tmp;
		for(int i=0;i<k;++i)tmp.push_back(s[x][i]);
		tmp.push_back(T);
		for(int i=k;i<s[x].size();++i)tmp.push_back(s[x][i]);
		s[x]=tmp;
		if(s[x].size()==4){
			int u=id[x]=++cnt;++cnt;
			sz[u]=sz[u+1]=2;
			co[u]=co[u+1]=co[x];
			for(int i=0;i<4;++i){
				int v=s[x][i];
				co[v]=(i>1);
				op1(u+co[v],v);
			}
			split(x,y,d);
		}
		return;
	}
	if(s[x].empty())s[x].push_back(++cnt);
	if(sz[x]==pw[d-1]*3+1)color(x,d);
	for(auto v:s[x]){
		if(k<=sz[v]){
			ins(v,x,d-1,k);
			if(sz[x]>3*pw[d-1])op1(id[x]+co[v],T);
			break;
		}
		k-=sz[v];
	}
	if(sz[x]>3*pw[d-1]){
		int c=3;
		while(c&&!s0[x].empty())op1(id[x],s0[x].back()),s0[x].pop_back(),--c;
		while(c&&!s1[x].empty())op1(id[x]+1,s1[x].back()),s1[x].pop_back(),--c;
	}
	if(sz[x]==pw[d])split(x,y,d);
}
void solve(int x,int l,int r){
	if(!T)init();
	sz[++T]=1,op1(T,T),sz[T]=1;
	ins(rt,0,10,x-1);
	query(rt,l,r);
}