//P3835
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10, P = N * 50;
int n, rt[N], x, y, z;
int ch[P][2], val[P], pri[P], siz[P], tot;

void upd(int x){
	siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
}
int nnd(int v){
	siz[++tot] = 1;
	val[tot] = v;
	pri[tot] = rand();
	return tot;
}
void cpy(int x, int y){
	ch[x][0] = ch[y][0];
	ch[x][1] = ch[y][1];
	val[x] = val[y];
	pri[x] = pri[y];
	siz[x] = siz[y];
}
int merge(int x, int y){
	if(!x || !y){
		return x + y;
	}
	if(pri[x] <= pri[y]){
		++ tot;
		cpy(tot, x);
		ch[tot][1] = merge(ch[tot][1], y);
		upd(tot);
		return tot;
	} else {
		++ tot;
		cpy(tot, y);
		ch[tot][0] = merge(x, ch[tot][0]);
		upd(tot);
		return tot;
	}
}
void split(int p, int k, int &x, int &y){
	if(!p){
		x = y = 0;
	} else {
		if(val[p] <= k){
			x = ++ tot;
			cpy(x, p);
			split(ch[x][1], k, ch[x][1], y);
			upd(x);
		} else {
			y = ++ tot;
			cpy(y, p);
			split(ch[y][0], k, x, ch[y][0]);
			upd(y);
		}
	}
}
int kth(int p, int k){
	while(true){
		if(k <= siz[ch[p][0]]){
			p = ch[p][0];
		} else if(k == siz[ch[p][0]] + 1){
			return p;
		} else {
			k -= (siz[ch[p][0]] + 1);
			p = ch[p][1];
		}
	}
}

void ins(int v, int k){
	split(rt[v], k, x, y);
	rt[v] = merge(merge(x, nnd(k)), y);
}
void del(int v, int k){
	split(rt[v], k, x, z);
	split(x, k-1, x, y);
	y = merge(ch[y][0], ch[y][1]);
	rt[v] = merge(merge(x, y), z);
}
int grk(int v, int k){
	split(rt[v], k-1, x, y);
	int ans = siz[x] + 1;
	rt[v] = merge(x, y);
	return ans;
}
int gvl(int v, int k){
	return val[kth(rt[v], k)];
}
int gpr(int v, int k){
	split(rt[v], k-1, x, y);
	int ans = val[kth(x, siz[x])];
	rt[v] = merge(x, y);
	return ans;
}
int gnx(int v, int k){
	split(rt[v], k, x, y);
	int ans = val[kth(y, 1)];
	rt[v] = merge(x, y);
	return ans;
}

int main(){
	srand(unsigned(time(NULL)));
	nnd(-2147483647);
	nnd(2147483647);
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i){
		int v, op, x;
		scanf("%d%d%d", &v, &op, &x);
		rt[i] = rt[v];
		if(op == 1){
			ins(i, x);
		} else if(op == 2){
			del(i, x);
		} else if(op == 3){
			printf("%d\n", grk(i, x));
		} else if(op == 4){
			printf("%d\n", gvl(i, x));
		} else if(op == 5){
			printf("%d\n", gpr(i, x));
		} else if(op == 6){
			printf("%d\n", gnx(i, x));
		}
	}
	return 0;
}