#include<stdio.h>

#include<algorithm>

#include<math.h>

#include<string.h>

using namespace std;

#define inf 1000000000

#define MAXN 1000100

int pa[MAXN],ch[MAXN][],ki[MAXN],pi[MAXN];

int root,cnt;

void Rotate(int x,int kind)

{

    int y=pa[x];

    int z=pa[y];

    ch[y][!kind]=ch[x][kind];

    pa[ch[x][kind]]=y;

    if(pa[y])ch[pa[y]][ch[pa[y]][]==y]=x;

    pa[x]=pa[y];

    ch[x][kind]=y;

    pa[y]=x;

}

void splay(int x,int goal)

{

    while(pa[x]!=goal)

    {

        if(pa[pa[x]]==goal)

        {

            Rotate(x,ch[pa[x]][]==x);

        }

        else

        {

            int y=pa[x];

            int kind=ch[pa[y]][]==y;

            if(ch[y][kind]==x)

            {

                Rotate(x,!kind);

                Rotate(x,kind);

            }

            else

            {

                Rotate(y,kind);

                Rotate(x,kind);

            }

        }

    }

    if(goal==)root=x;

}

void newnode(int &x,int k,int p,int father)

{

    x=++cnt;

    pa[x]=father;

    ch[x][]=ch[x][]=;

    pi[x]=p;

    ki[x]=k;

}

void Insert(int k,int p)

{

    int rt=root;

    int r=root;

    while(rt!=)

    {

        r=rt;

        if(pi[rt]<p)rt=ch[rt][];

        else rt=ch[rt][];

    }

    newnode(ch[r][pi[r]<p],k,p,r);

    splay(ch[r][pi[r]<p],root);

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

}

int f_max(int x)

{

    while(ch[x][])

        x=ch[x][];

    if(x==root)

        root=ch[x][];

    ch[pa[x]][]=ch[x][];

    pa[ch[x][]]=pa[x];

    return ki[x];

}

int f_min(int x)

{

    while(ch[x][])

        x=ch[x][];

    if(x==root)

        root=ch[x][];

    ch[pa[x]][]=ch[x][];

    pa[ch[x][]]=pa[x];

    return ki[x];

}

int main()

{

    root=cnt=;

    int n;

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

    {

        if(n==)

        {

            int k,p;

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

            Insert(k,p);

        }

        else if(n==)

            printf("%d\n",f_max(root));

        else

            printf("%d\n",f_min(root));

    }

    return ;

}