#include<cstdio>
#include<iostream>
#define cp freopen
#define Node node*
#define MAX 1000010
#define inf (MAX*99)
#define rep(i,a,b) for (int i=a;i<=b;i++)
using namespace std;

class splay
{
      struct node
      {
            int k,v,s;
            bool d;
            node *c[2],*p;
            void sc(node *_c,bool d)
            {
                  c[d]=_c;
                  _c->p=this;
                  _c->d=d; 
            }
      }*root,*null,*stack[MAX],*now,data[MAX],*tmp; 
      int top;  
      Node new_node(int k,int v)
      {
            if (top) 
                  tmp=stack[top--];
            else
                  tmp=now++; 
            tmp->k=k;
            tmp->v=v;
            tmp->s=1; 
            tmp->c[0]=tmp->c[1]=null;
            return tmp; 
      }
      void del_node(Node c)
      {
            stack[++top]=c; 
      }
      Node insert(int v,int k)
      {
            for(Node t=root;t->k!=k;)
            {
                  int d=k>t->k; 
                  if (t->c[d]==null)
                  {
                        Node p=new_node(k,v); 
                        t->sc(p,d);
                        upd(t); 
                        return t; 
                  }
                  t=t->c[d]; 
            }
      }
      Node select(int k)
      {
            for(Node t=root->c[1];;)
            {
                  int r=t->c[0]->s;
                  if (r==k)
                        return t;
                  t=t->c[k>r];
                  if (k>r) 
                        k-=r+1; 
            } 
      }
      Node Delete(Node k)
      {
            Node t; 
            Node p=find(k->k); 
            while (p->c[0]!=null)
                  rot(p->c[0]);
            if (p->c[1]!=null)
            {
                  p->p->sc(p->c[1],p->d);
                  t=p->c[1]; 
            }
            else
            {
                  p->p->c[p->d]=null;
                  t=p->p;
            }
            upd(p->p);               
            del_node(p); 
            return t; 
      }
      void upd(Node x)
      {
            x->s=x->c[1]->s+x->c[0]->s+1; 
      }
      void rot(Node x)
      {
            Node p=x->p;
            int d=x->d; 
            p->p->sc(x,p->d);
            p->sc(x->c[!d],d);
            x->sc(p,!d);   
            upd(p); 
            upd(x); 
      }
      void spl(Node x,Node f)
      {
            while (x->p!=f)
            {
                  if (x->p->p==f)
                        rot(x);
                  else
                        if (x->d==x->p->d)
                              rot(x->p),rot(x);
                        else
                              rot(x),rot(x);
            }
      }
      public:
            int all;  
            splay()
            {
                  top=all=0; 
                  now=data;
                  null=new_node(0,0);
                  null->s=0;
                  root=new_node(-inf,0);
                  root->p=root; 
            }
            Node find(int x)
            {
                  Node t=root->c[1];
                  while (t!=null&&t->k!=x)
                        t=t->c[x>t->k]; 
                  return t; 
            }
            void ins(int v,int k)
            {
                  Node p=insert(v,k);
                  spl(p,root); 
                  all++; 
            }
            void del(Node p)
            {
                  Node t=Delete(p);
                  spl(t,root); 
            }
            void sel(int x)
            {
                  if (x==0)
                  {
                        cout<<0<<endl;
                        return;
                  }
                  Node p=select(x-1);
                  del(p); 
                  cout<<p->v<<endl;  
                  all--; 
            }
}*sp; 

int main()
{
      cp("1.in","r",stdin);
      cp("1.out","w",stdout); 
      
      int k; 
      sp=new splay; 
      while (scanf("%d",&k)!=EOF)
      {
            if (k==0)
                  break;
            if (k==1)
            {
                  int x,y;
                  scanf("%d %d",&x,&y);
                  sp->ins(x,y); 
            }
            if (k==2)
                  sp->sel(sp->all); 
            if (k==3)
                  sp->sel(1); 
      }
      
      return 0;  
}