#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int map[10001000];
int n,m;
void swap(int &x,int &y){int z=x;x=y;y=z;}
struct Heap_Changing_Lazy{
	int heap[200200],top;
	char delmark[10001000];
	void insert(int x){
	    if(delmark[x]){
			delmark[x]--;
			return ; 
		}
	    heap[++top]=x;int t=top;while(t>1&&heap[t]>heap[t>>1])swap(heap[t],heap[t>>1]),t>>=1;
	}//插入，如果有delmark的话直接delmark[x]--
	void pop()
	{
	    int t=2;
	    heap[1]=heap[top];heap[top--]=0;
	    while(t<=top)
	    {
	        if(heap[t]<heap[t+1]&&t<top)t++;
	        if(heap[t]>heap[t>>1])swap(heap[t],heap[t>>1]),t<<=1;
	        else break;
	    }
	}//弹顶
	int heaptop(){
		int t;
		while(delmark[heap[1]]) 
			delmark[heap[1]]--,pop();//把有删除标记的堆顶全部删除
		t=heap[1];
		if(top)pop();
		return t; 
	}
}Maxheap,Minheap;
int main()
{
	int p,x,y,t;
	while(scanf("%d",&p),p)
	{
		switch(p)
		{
			case 1:scanf("%d%d",&x,&y),map[y]=x,Maxheap.insert(y),Minheap.insert(10000001-y);break;
			case 2:t=Maxheap.heaptop(),printf("%d\n",map[t]),Minheap.delmark[10000001-t]++;break;
			case 3:t=10000001-Minheap.heaptop(),printf("%d\n",map[t]),Maxheap.delmark[t]++;break;
		}
	}
}