#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
const int NMax=100100;
struct _node {
	bool InTree;
    int key,key1,num,size;
    _node *left,*right;
	inline int lsize(){return left?left->size:0;}
	inline int rsize(){return right?right->size:0;}
};
struct Treap {
	_node *Tree;_node pool[NMax];
	int _L,cntleft;
	Treap(){Tree=NULL;_L=0;cntleft=0;}
	inline _node *_RightR(_node *p,_node *l) {p->left=l->right;l->right=p;p->size=p->lsize()+p->rsize()+1;l->size=l->lsize()+l->rsize()+1;return l;}
	inline _node *_LeftR(_node *p,_node *r) {p->right=r->left;r->left=p;p->size=p->lsize()+p->rsize()+1;r->size=r->lsize()+r->rsize()+1;return r;}
	inline void Ins(int x,int y) {Tree=_Ins(x,y,Tree);}
	_node* _Ins(int x,int x1,_node *p) {
		if(!p){
			p=&pool[_L++];
			p->num=x;p->InTree=1;p->size=1;p->key1=x1;
			p->key=(rand()<<16)^(rand()<<8)^(rand());
			p->left=p->right=NULL;
			return p;
		}
		if(x>=p->num) {
			p->right=_Ins(x,x1,p->right);
			if(p->right->key<p->key) p=_LeftR(p,p->right);
			p->size=p->lsize()+p->rsize()+1;
		}else{
			p->left=_Ins(x,x1,p->left);
			if(p->left->key<p->key) p=_RightR(p,p->left);
		    p->size=p->rsize()+p->lsize()+1;
        }
		return p;
	}
	//inline void Del(int x){if(_Find(x,Tree))Tree=_Del(x,Tree);}
	_node *_Del(int x,int x1,_node *p) {
        if(p->num==x&&p->key1==x1) {
            if(!p->left) return p->right;
            else if(!p->right) return p->left;
            else {
                if(p->left->key>p->right->key) {
                    p=_LeftR(p,p->right);p->size--;
					p->left=_Del(x,x1,p->left);
					p->size=p->lsize()+p->rsize()+1;
                    return p;
                }else {
                    p=_RightR(p,p->left);p->size--;
                    p->right=_Del(x,x1,p->right);
					p->size=p->lsize()+p->rsize()+1;
                    return p;
                }
            }
        }else if(x>=p->num) {
            p->size--;p->right=_Del(x,x1,p->right);
			p->size=p->lsize()+p->rsize()+1;
            return p;
        }else if(x<p->num) {
            p->size--;p->left=_Del(x,x1,p->left);
			p->size=p->lsize()+p->rsize()+1;
            return p;
        }
    }
	inline bool Find(int x) {return _Find(x,Tree);}
	_node *_Find(int x,_node *p) {
		while(p&&(p->num!=x||!p->InTree)) {
			if(x>p->num) p=p->right;
			else p=p->left;
		}
		return p;
	}
	inline int Findidx(int k){_node *tmp=_Findidx(k,Tree);return tmp?tmp->num:(~0u>>1);}
	_node *_Findidx(int k,_node *p) {
		if(!p) return NULL;
		p->size=p->lsize()+p->rsize()+1;
		if(p->rsize()+1==k) {return p;}
		if(k<=p->rsize()) {return _Findidx(k,p->right);}
		if(k>p->rsize()+1) {return _Findidx(k-p->rsize()-1,p->left);}
	}
	inline int Lookup() {return _Lookup(Tree);}
	int _Lookup(_node *p){
		int ret=1;
		if(!p->InTree) ret=0;
		if(p->left) ret+=_Lookup(p->left);
		if(p->right) ret+=_Lookup(p->right);
		return ret;
	}
	inline int Add(int x){if(Tree) Tree=_Add(x,Tree);}
	_node *_Add(int x,_node *p) {
		p->num+=x;
		if(p->left) p->left=_Add(x,p->left);
		if(p->right) p->right=_Add(x,p->right);
		if(p)p->size=p->lsize()+p->rsize()+1;
		return p;
	}
	int delque[NMax],L;
	//void _procque() {for(int i=0;i<L;i++) Tree=_Del(delque[i],Tree);}
	//inline void Out(int k){L=0;if(Tree) Tree=_Out(k,Tree);_procque();}
	_node *_Out(int k,_node *p) {
		if(p->num<k) {cntleft++;delque[L++]=p->num;}
		if(p->left) p->left=_Out(k,p->left);
		if(p->right) p->right=_Out(k,p->right);
		p->size=p->lsize()+p->rsize()+1;
		return p;
	}
	inline int Max() {_node *p=_Max(Tree);int ret=p?p->key1:0;if(p)Tree=_Del(p->num,p->key1,Tree);return ret;}
	_node *_Max(_node *p) {
		if(!p) return NULL;
		while(p->right) p=p->right;
		return p;
	}
	inline int Min() {_node *p=_Min(Tree);int ret=p?p->key1:0;if(p)Tree=_Del(p->num,p->key1,Tree);return ret;}
	_node *_Min(_node *p) {
		if(!p) return NULL;
		while(p->left) p=p->left;
		return p;
	}
};
Treap treap;
int N,Min;
int main()
{
	int a;
	while(scanf("%d",&a),a) {
		if(a==2) printf("%d\n",treap.Max());
		else if(a==3) printf("%d\n",treap.Min());
		else {
			int x,y;
			scanf("%d%d",&x,&y);
			treap.Ins(y,x);
		}
	}
	getchar();getchar();
	return 0;
}