Code

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
/*
fhq_treap×ö·¨
fhq_treap YYDS!±ÈSplayºÃÓöàÁË 
*/
using namespace std;
using namespace __gnu_pbds;
/* --------------- fast io --------------- */ // begin
namespace Fread {
  const long long SIZE = 1 << 21;
  char buf[SIZE], *S, *T;
  inline char getchar() {
     if (S == T) {
        T = (S = buf) + fread(buf, 1, SIZE, stdin);
        if (S == T) return EOF;
     }
     return *S++;
  }
} // namespace Fread
namespace Fwrite {
  const long long SIZE = 1 << 21;
  char buf[SIZE], *S = buf, *T = buf + SIZE;
  inline void flush() {
     fwrite(buf, 1, S - buf, stdout);
     S = buf;
  }
  inline void putchar(char c) {
     *S++ = c;
     if (S == T) flush();
  }
  struct NTR {
     ~ NTR() { flush(); }
  }ztr;
} // namespace Fwrite
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
namespace Fastio {
  struct Reader {
     template<typename T>
     Reader& operator >> (T& x) {
        char c = getchar();
        T f = 1;
        while (c < '0' || c > '9') {
	if (c == '-') f = -1;
	c = getchar();
        }
        x = 0;
        while (c >= '0' && c <= '9') {
	x = x * 10 + (c - '0');
	c = getchar();
        }
        x *= f;
        return *this;
     }
     Reader& operator >> (char& c) {
        c = getchar();
        while (c == '\n' || c == ' ') c = getchar();
        return *this;
     }
     Reader& operator >> (char* str) {
        long long len = 0;
        char c = getchar();
        while (c == '\n' || c == ' ') c = getchar();
        while (c != '\n' && c != ' ') {
	str[len++] = c;
	c = getchar();
        }
        str[len] = '\0';
        return *this;
     }
     Reader(){}
  }cin;
  const char endl = '\n';
  struct Writer {
     template<typename T>
     Writer& operator << (T x) {
        if (x == 0) { putchar('0'); return *this; }
        if (x < 0) { putchar('-'); x = -x; }
        static long long sta[45];
        long long top = 0;
        while (x) { sta[++top] = x % 10; x /= 10; }
        while (top) { putchar(sta[top] + '0'); --top; }
        return *this;
     }
     Writer& operator << (char c) {
        putchar(c);
        return *this;
     }
     Writer& operator << (char* str) {
        long long cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
     }
     Writer& operator << (const char* str) {
        long long cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
     }
     Writer(){}
  }cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end
template<class T>T Min(register T a,register T b){
	return a<b?a:b;
}
template<class T>T Max(register T a,register T b){
	return a>b?a:b;
}
template<class T>T Abs(register T a){
	return a>0?a:-a;
}
template<class T>void Swap(register T &a,register T &b){
	T t=a;
	a=b;
	b=t;
}
using namespace std;
const long long N=25005000;
const long long INF=2147483647;
struct Tree{
    long long l,r;
    long long val,key;
    long long sz;
};
Tree tr[N];
long long n;
long long root[N];
long long idx;
long long x,y,z;
long long get_node(long long v){
    tr[++idx].val=v;
    tr[idx].key=rand();
    tr[idx].sz=1;
    return idx;
}
void pushup(long long u){
    tr[u].sz=1;
    if(tr[u].l){
    	tr[u].sz+=tr[tr[u].l].sz;
	}
	if(tr[u].r){
		tr[u].sz+=tr[tr[u].r].sz;
	}
}
void split(long long u,long long v,long long &x,long long &y){
    if(!u){
        x=y=0;
        return ;
    }
    if(tr[u].val<=v){
    	x=get_node(0);
    	x=u;
        split(tr[x].r,v,tr[x].r,y);
        pushup(x);
    }
	else{
		y=get_node(0);
        y=u;
        split(tr[y].l,v,x,tr[y].l);
        pushup(y);
    }
}
long long merge(long long x,long long y){
    if(!x || !y){
    	return x+y;
	}
    if(tr[x].key>tr[y].key){
    	long long New=get_node(0);
    	tr[New]=tr[x];
        tr[New].r=merge(tr[New].r,y);
        pushup(New);
        return New;
    }
	else{
		long long New=get_node(0);
		tr[New]=tr[y];
        tr[New].l=merge(x,tr[New].l);
        pushup(New);
        return New;
    }
}
void insert(long long v,long long p){
    split(root[p],v,x,y);
    root[p]=merge(merge(x,get_node(v)),y);
}
void remove(long long v,long long p){
    split(root[p],v,x,z);
    split(x,v-1,x,y);
    y=merge(tr[y].l,tr[y].r);
    root[p]=merge(merge(x,y),z);
}
void get_rank_by_key(long long key,long long p){
    split(root[p],key-1,x,y);
    cout << tr[x].sz+1 << endl;
    root[p]=merge(x,y);
}
void get_key_by_rank(long long rank,long long p){
    long long u=root[p];
    while(u){
        if(tr[tr[u].l].sz>=rank){
        	u=tr[u].l;
		}
        else if(tr[tr[u].l].sz+1==rank){
            cout << tr[u].val << endl;
            return ;
        }
        else{
        	rank-=tr[tr[u].l].sz+1;
			u=tr[u].r;
		}
    }
}
void get_prev(long long v,long long p){
    split(root[p],v-1,x,y);
    if(x==0){
    	cout << -INF << endl;
    	return ;
	}
    long long k=x;
    while(tr[k].r){
    	k=tr[k].r;
	}
    cout << tr[k].val << endl;
    root[p]=merge(x,y);
}
void get_next(long long v,long long p){
    split(root[p],v,x,y);
    if(y==0){
    	cout << INF << endl;
    	return ;
	}
    long long k=y;
    while(tr[k].l){
    	k=tr[k].l;
	}
    cout << tr[k].val << endl;
    root[p]=merge(x,y);
}
int main(){
	cin >> n;
    long long id,op,x;
    for(long long i=1;i<=n;i++){
    	cin >> id >> op >> x;
    	root[i]=root[id];
        if(op==1){
        	insert(x,i);
		}
        else if(op==2){
        	remove(x,i);
		}
        else if(op==3){
        	get_rank_by_key(x,i);
		}
        else if(op==4){
        	get_key_by_rank(x,i);
		}
        else if(op==5){
        	get_prev(x,i);
		}
        else{
        	get_next(x,i);
		}
    }
    return 0;
}