#include<cstdio>

#include<iostream>

using namespace std;

#define maxn 1000005

int root;

int tot=;

int ch[maxn][],par[maxn];

int cnt[maxn],size[maxn];

int val[maxn],dat[maxn];

void pushup(int x)

{

    size[x]=cnt[x]+size[ch[x][]]+size[ch[x][]];

}///size信息

bool which(int x)

{

    return ch[par[x]][]==x;

}

void rotate(int x)

{

    int y=par[x],z=par[y];///?

    int w=which(x);

    int t=ch[x][w^];

    par[t]=y;

    ch[y][w]=t;

    //par[t]=y;

    par[x]=z;

    ch[z][which(y)]=x;

    //par[x]=z;

    par[y]=x;

    ch[x][w^]=y;

    //par[y]=x;

    pushup(y);

    pushup(x);

}

void splay(int x,int goal=)

{

    if(x==)return;

    int y,z;

    while(par[x]!=goal)///为什么不是x

    {

        // cout<<"PAR"<<par[x]<<endl;

        y=par[x],z=par[y];

        //cout<<x<<y<<z<<"YZ"<<endl;

        if(z!=goal) ///???

        {

            if(which(x)==which(y))

            {

                rotate(y);

            }

            else rotate(x);

        }

        rotate(x);

        // x=par[x];

        // y=par[y];

    }

    if(!goal)root=x;

}

void find(int x)

{

    int cur=root;

    while(ch[cur][x>val[cur]]&&x!=val[cur])

    {

        cur=ch[cur][x>val[cur]];

    }///为什么不维护父节点了？

    splay(cur);

}

int pre(int x)

{

    find(x);

    int cur=ch[root][];

    if(!cur)return ;///直接返回0

    //cout<<root<<" pre "<<ch[root][0]<<endl;

    while(ch[cur][])

    {

        cur=ch[cur][];

    }

    return cur;

}

int succ(int x)

{

    find(x);

    int cur=ch[root][];

    if(!cur)return ;

    //cout<<root<<" pre "<<ch[root][1]<<endl;

    while(ch[cur][])

    {

        cur=ch[cur][];

    }

    return cur;

}

void dfs(int cur)

{

    //cout<<cur<<"cur"<<" ch "<<ch[cur][1]<<endl;

    if(ch[cur][])dfs(ch[cur][]);

    cout<<val[cur]<<" "<<dat[cur]<<'\n';

    if(ch[cur][])dfs(ch[cur][]);

}

void del(int x)

{

    //cout<<root<<"END"<<endl;

    int p=pre(x),s=succ(x);///后缀为0？？？前驱为0？？？

    // cout<<p<<" PS "<<s<<endl;

    if(!s)

    {

        if(!p)

        {

            ch[root][]=ch[root][]=root=;///只有一个点

            return;

        }

        splay(p);///没有后缀

        ch[root][]=;

        return;

    }///???

    //cout<<x<<endl;

    //cout<<p<<s<<endl;

    splay(p);

    splay(s,p);

    int de=ch[s][];

    if(cnt[de]>)

    {

        cnt[de]--;

        splay(de);

    }

    else

        ch[s][]=;

    //par[ch[root][1]]=root;

    //pushup(root);

}

void ins(int x,int d)

{

    int cur=root,p=;///维护父节点信息

    while(cur&&(x!=val[cur]))

    {

        p=cur;

        cur=ch[cur][x>val[cur]];///>号

    }

    if(cur)

    {

        cnt[cur]++;

    }

    else

    {

        cur=++tot;

        //cout<<p<<"父亲"<<endl;

        if(p)ch[p][x>val[p]]=cur;///判一下p是否为0

        ch[cur][]=ch[cur][]=;

        par[cur]=p;///注意维护下父节点

        val[cur]=x;

        dat[cur]=d;

        size[cur]=;

        cnt[cur]=;

        // dfs(root);

        splay(cur);

    }

    // cout<<"DFS"<<endl;

    //dfs(root);

}

int mi()

{

    int cur=root;

    if(!cur)return ;

    while(ch[cur][])

    {

        cur=ch[cur][];

    }

    int ans=dat[cur];

    del(val[cur]);

    return ans;

}

int ma()

{

    int cur=root;

    if(!cur)return ;

    while(ch[cur][])

    {

        cur=ch[cur][];

    }

    int ans=dat[cur];

    //cout<<ans<<endl;

    del(val[cur]);

    //dfs(root);

    return ans;

}

int main()

{

    int n,d,p;

    while(scanf("%d",&n)!=EOF)

    {

        if(n==)break;

        else if(n==)

        {

            scanf("%d%d",&d,&p);

            ins(p,d);

        }

        else if(n==)

        {

            cout<<ma()<<'\n';

        }

        else if(n==)

        {

            cout<<mi()<<'\n';

        }

    }

}