#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;
}