#include<bits/stdc++.h>
#define N 500010
using namespace std;
const int inf=pow(2,31)-1;
struct node
{
	int l,r;
	int size,rnd,v;
}t[500005*80];
int cnt;
void update(int k)
{
	t[k].size=t[t[k].l].size+t[t[k].r].size+1;
}
void newnode(int &k,int w)
{
	t[k=++cnt].v=w;
	t[k].size=1;//加入一个点！	
	t[k].rnd=rand();
} 
int merge(int a,int b)//a上的值小于b上的值 
{
	if(!a||!b) return a+b;
	if(t[a].rnd>t[b].rnd)
		{
			int p=++cnt;
			t[p]=t[a];
			t[p].r=merge(t[p].r,b);
			update(p);
			return p;
		}
	int p=++cnt;
	t[p]=t[b];
//	t[p].l=merge(t[p].l,a);//这里不是merge(t[p].l,a)而是merge(a,t[p].l)!因为保证左小于右！！！ 
	t[p].l=merge(a,t[p].l);
	update(p);
	return p;	
}
void split(int now,int k,int &x,int &y)// 把now这颗树分作x和y两颗子树 
{
	if(!now) x=y=0;//重要！！！！ 
	else
		{
			if(t[now].v<=k)
			{
				x=++cnt,t[x]=t[now];
				split(t[x].r,k,t[x].r,y);
				update(x);//更新后都要update！！ 
			}
			else
			{
				y=++cnt,t[y]=t[now];
				split(t[y].l,k,x,t[y].l);
				update(y);//为什么只update一个！？因为把y的儿子改变了！！所以要更新y！！	
			}
		}
}
int read()
{
	int sum=0,f=1;
	char ch=getchar();
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-') ch=getchar(),f=-1; 
	while(ch<='9'&&ch>='0')
		{
			sum=sum*10+ch-'0';
			ch=getchar();
		}
	return sum*f; 
} 
int n;
int a,b,c;
int sta[N];
void insert(int &root,int w)
{
	int x=0,y=0,z=0;
	split(root,w,x,y);
	newnode(z,w);
	root=merge(merge(x,z),y);
}
void Delete(int &root,int w)
{
	int x=0,y=0,z=0;
	split(root,w,x,z);
	split(x,w-1,x,y);
	//此时y是一棵权值全为w的树
	y=merge(t[y].l,t[y].r);//删掉其中一个权值 
	root=merge(merge(x,y),z); 
}
int getrank(int root,int w)
{
	int x=0,y=0;
	split(root,w-1,x,y);
	return t[x].size+1; 
}
int getval(int root,int w)
{
	int g=t[t[root].l].size;
	if(g>=w) return getval(t[root].l,w); 
	if(g+1==w) return t[root].v;
	return getval(t[root].r,w-g-1);
}
int getpre(int root,int w)
{
	int x=0,y=0;
	split(root,w-1,x,y);
	if(!x) return -inf;
	while(t[x].r) x=t[x].r;
	return t[x].v;
}
int gethou(int root,int w)
{
	int x=0,y=0;
	split(root,w+1,x,y);
	if(!y) return inf;
	while(t[y].l) y=t[y].l;
	return t[y].v;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		{
			a=read(),b=read(),c=read();
			sta[i]=sta[a];	
			if(b==1) insert(sta[i],c);
			else if(b==2) Delete(sta[i],c);
			else if(b==3) cout<<getrank(sta[i],c)<<'\n';
			else if(b==4) cout<<getval(sta[i],c)<<'\n';
			else if(b==5) cout<<getpre(sta[i],c)<<'\n';
			else cout<<gethou(sta[i],c)<<'\n';
		}
	return 0;
}