#include<bits/stdc++.h> #define int long long using namespace std; namespace Fast{ inline int fr(){ register int x = 0,f = 1; static char c = getchar(); while (c < '0' || c > '9'){ if (c == '-'){ f = -1; } c = getchar(); } while (c >= '0' && c <= '9'){ x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * f; } inline void fw(int x){ if (x < 0){ putchar('-'); x = -x; } if (x > 9){ fw(x / 10); } putchar(x % 10 + 48); } } using namespace Fast; const int maxn = 4e7 + 5; int psz,key[maxn],pri[maxn],ch[maxn][2],siz[maxn],root[1919810]; int copy(int u){ int v = ++psz; key[v] = key[u]; ch[v][0] = ch[u][0]; ch[v][1] = ch[u][1]; pri[v] = pri[u]; siz[v] = siz[u]; return v; } int node(int k){ int u = ++psz; key[u] = k; pri[u] = rand(); ch[u][0] = ch[u][1] = 0; siz[u] = 1; return u; } void maintain(int u){ siz[u] = siz[ch[u][0]] + siz[ch[u][1]] + 1; } void split(int u,int k,int &l,int &r){ if (u == 0){ l = r = 0; return ; } u = copy(u); if (k <= key[u]){ split(ch[u][0],k,l,ch[u][0]); r = u; } else{ split(ch[u][1],k,ch[u][1],r); l = u; } maintain(u); } int merge(int u,int v){ if (u == 0 || v == 0){ return u + v; } if (pri[u] < pri[v]){ u = copy(u); ch[u][1] = merge(ch[u][1],v); maintain(u); return u; } else{ v = copy(v); ch[v][0] = merge(u,ch[v][0]); maintain(v); return v; } } void erase(int &root,int k){ int l,u,r; split(root,k,l,r); split(r,k + 1,u,r); root = merge(merge(l,merge(ch[u][0],ch[u][1])),r); } int Rank(int root,int k){ int u = root,ret = 0; while (u){ if (k <= key[u]){ u = ch[u][0]; } else{ ret += siz[ch[u][0]] + 1; u = ch[u][1]; } } return ret + 1; } int Select(int root,int k){ int u = root; while (u){ if (siz[ch[u][0]] + 1 == k){ return key[u]; } if (k <= siz[ch[u][0]]){ u = ch[u][0]; } else{ k -= siz[ch[u][0]] + 1; u = ch[u][1]; } } return 0; } int Prev(int root,int k){ return Select(root,Rank(root,k) - 1); } int Next(int root,int k){ return Select(root,Rank(root,k + 1)); } void insert(int &root,int k){ int l,r; split(root,k,l,r); root = merge(merge(l,node(k)),r); } void po(int x){ fw(x); puts(""); } signed main(){ int n = fr(); for (int i = 1;i <= n;i++){ int v,opt,x; v = fr(),opt = fr(),x = fr(); root[i] = root[v]; if (opt == 1){ insert(root[i],x); } else if (opt == 2){ erase(root[i],x); } else if (opt == 3){ po(Rank(root[i],x)); } else if (opt == 4){ po(Select(root[i],x)); } else if (opt == 5){ po(Prev(root[i],x)); } else{ po(Next(root[i],x)); } } return 0; }