//

//  main.cpp

//  splay

//

//  Created by 陈加寿 on 16/3/25.

//  Copyright © 2016年 chenhuan001. All rights reserved.

//

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define MAXN 1001000

struct Splay_Tree

{

    int cnt, rt;

    struct node

    {

        int K;

        int key, size, fa, son[];

        void set(int _key, int _size, int _fa,int _K)

        {

            K = _K;

            key=_key;

            size=_size;

            fa=_fa;

            son[]=son[]=;

        }

    }T[MAXN];

    inline void init()

    {

        cnt = ;

        rt = ;

    }

    inline void PushUp(int x)

    {

        T[x].size=T[T[x].son[]].size+T[T[x].son[]].size+;

    }

    inline void Rotate(int x, int p) //0左旋 1右旋

    {

        int y=T[x].fa;

        T[y].son[!p]=T[x].son[p];

        T[T[x].son[p]].fa=y;

        T[x].fa=T[y].fa;

        if(T[x].fa)

            T[T[x].fa].son[T[T[x].fa].son[] == y]=x;

        T[x].son[p]=y;

        T[y].fa=x;

        PushUp(y);

        PushUp(x);

    }

    void Splay(int x, int To) //将x节点插入到To的子节点中

    {

        while(T[x].fa != To)

        {

            if(T[T[x].fa].fa == To)

                Rotate(x, T[T[x].fa].son[] == x);

            else

            {

                int y=T[x].fa, z=T[y].fa;

                int p=(T[z].son[] == y);

                if(T[y].son[p] == x)

                    Rotate(x, !p), Rotate(x, p); //之字旋

                else

                    Rotate(y, p), Rotate(x, p); //一字旋

            }

        }

        if(To == ) rt=x;

    }

    int find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处

    {

        int x=rt;

        while(x && T[x].key != key)

            x=T[x].son[key > T[x].key];

        if(x) Splay(x, );

        return x;

    }

    int prev() //返回比根值小的最大值 若无返回0 若有将其转移到根处

    {

        int x=T[rt].son[];

        if(!x) return ;

        while(T[x].son[])

            x=T[x].son[];

        Splay(x, );

        return x;

    }

    int next() //返回比根值大的最小值 若无返回0 若有将其转移到根处

    {

        int x=T[rt].son[];

        if(!x) return ;

        while(T[x].son[])

            x=T[x].son[];

        Splay(x, );

        return x;

    }

    void Insert(int key,int K) //插入key 并且将该节点转移到根处

    {

        if(!rt)

            T[rt = cnt++].set(key, , , K);

        else

        {

            int x=rt, y=;

            while(x)

            {

                y=x;

                x=T[x].son[key > T[x].key];

            }

            T[x = cnt++].set(key, , y, K);

            T[y].son[key > T[y].key]=x;

            Splay(x, );

        }

    }

    void Delete(int key) //删除值为key的节点 若有重点只删其中一个 x的前驱移动到根处

    {

        int x=find(key);

        if(!x) return;

        int y=T[x].son[];

        while(T[y].son[])

            y=T[y].son[];

        int z=T[x].son[];

        while(T[z].son[])

            z=T[z].son[];

        if(!y && !z)

        {

            rt=;

            return;

        }

        if(!y)

        {

            Splay(z, );

            T[z].son[]=;

            PushUp(z);

            return;

        }

        if(!z)

        {

            Splay(y, );

            T[y].son[]=;

            PushUp(y);

            return;

        }

        Splay(y, );

        Splay(z, y);

        T[z].son[]=;

        PushUp(z);

        PushUp(y);

    }

    int GetPth(int p) //获得第p小的节点 并将其转移到根处

    {

        if(!rt) return ;

        int x=rt;

        while(x)

        {

            if(p == T[T[x].son[]].size+)

                break;

            if(p>T[T[x].son[]].size+)

            {

                p-=T[T[x].son[]].size+;

                x=T[x].son[];

            }

            else

                x=T[x].son[];

        }

        Splay(x, );

        return x;

    }

    int GetRank(int key) //获得值<=key的节点个数 并将其转移到根处 若<key只需将<=换为<

    {

        if(!rt) return ;

        int x=rt, ret=, y=;

        while(x)

        {

            y=x;

            if(T[x].key <= key)

            {

                ret+=T[T[x].son[]].size+;

                x=T[x].son[];

            }

            else

                x=T[x].son[];

        }

        Splay(y, );

        return ret;

    }

}spt;

int main() {

    int sign;

    spt.init();

    int cnt=;

    while (scanf("%d",&sign) && sign) {

        if(sign == )//插入一个值

        {

            int k,p;

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

            spt.Insert(p,k);

            cnt++;

        }

        else if(sign == )

        {

            //找出最高优先级。

            if(spt.rt == )

            {

                printf("0\n");

            }

            else

            {

                int id = spt.GetPth(cnt);

                printf("%d\n",spt.T[id].K);

                spt.Delete(spt.T[id].key);

                cnt--;

            }

        }

        else if(sign == )

        {

            if(spt.rt == )

            {

                printf("0\n");

            }

            else

            {

                int id = spt.GetPth();

                printf("%d\n",spt.T[id].K);

                spt.Delete(spt.T[id].key);

                cnt--;

            }

        }

    }

    return ;

}