#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct tree{
	int ls,rs,siz,val,key;
}c[N*50];
int n,st[N],tot,top,root;
int news(int x = 0){
	int id;
	if(top)id=st[top--];
	else id=++tot;
	c[id]=(tree){0,0,1,x,rand()*rand()};
	return id;
}
void pushup(int x){
	c[x].siz=c[c[x].ls].siz+c[c[x].rs].siz+1;
}
void split(int now,int &x,int &y,int k){
	if(!now){
		x=y=0;
		return;
	}
	if(c[now].val<=k){
		x=news(),c[x]=c[now];
		split(c[x].rs,c[x].rs,y,k);
		pushup(x);
	}
	else{
		y=news(),c[y]=c[now];
		split(c[y].ls,x,c[y].ls,k);
		pushup(y);
	}
}
void split1(int now,int &x,int &y,int k){
	if(!now){
		x=y=0;
		return;
	}
	if(c[c[now].ls].siz<k){
		x=news(),c[x]=c[now];
		split1(c[x].rs,c[x].rs,y,k-c[c[x].ls].siz-1);
		pushup(x);
	}
	else{
		y=news(),c[y]=c[now];
		split1(c[y].ls,x,c[y].ls,k);
		pushup(y);
	}
}
void merge(int &rt,int x,int y){
	if(!x||!y){
		rt=x^y;
		return;
	}
	if(c[x].key<c[y].key){
		rt=news(),c[rt]=c[x];
		merge(c[rt].rs,c[rt].rs,y);
		pushup(rt);
	}
	else{
		rt=news(),c[rt]=c[y];
		merge(c[rt].ls,x,c[rt].ls);
		pushup(rt);
	}
//	pushup(rt);
}
void insert(int &root,int x){
	int id=news(x),a,b;
	split(root,a,b,x);
	merge(a,a,id);
	merge(root,a,b);
}
void del(int &root,int x){
	int a,b,c;
	split(root,a,b,x-1);
	split1(b,b,c,1);
	if(b)st[++top]=b;
	merge(root,a,c);
}
int query(int now,int k){
	if(c[c[now].ls].siz>=k)return query(c[now].ls,k);
	else if(c[c[now].ls].siz+1==k)return c[now].val;
	else if(c[c[now].ls].siz<k)return query(c[now].rs,k-c[c[now].ls].siz-1);
	else return -1;
}
int queryk(int &root,int x){
	int a,b;
	split(root,a,b,x-1);
	int tmp=c[a].siz+1;
	merge(root,a,b);
	return tmp;
}
int querylast(int &root,int x){
	int a,b,tmp;
	split(root,a,b,x-1);
	if(!a)tmp=-2147483647;
	else tmp=query(a,c[a].siz);
	merge(root,a,b);
	return tmp;
}
int querypre(int &root,int x){
	int a,b,tmp;
	split(root,a,b,x);
	if(!b)tmp=2147483647;
	else tmp=query(b,1);
	merge(root,a,b);
	return tmp;
}
int op,x,tlh,rt[N];
int main(){
	srand(114514);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> tlh >>  op >> x;
		rt[i]=rt[tlh];
		if(op==1)insert(rt[i],x);
		else if(op==2)del(rt[i],x);
		else if(op==4)cout << query(rt[i],x) << "\n";
		else if(op==3)cout << queryk(rt[i],x) << "\n";
		else if(op==5)cout << querylast(rt[i],x) << "\n";
		else if(op==6)cout << querypre(rt[i],x) << "\n";
	}
	return 0;
}