> #include <iostream>
> #include <algorithm>
> #include <cstring>
> #include <cstdio>
> #define keyTree (ch[ ch[root][1] ][0])
> const int maxn = 1222222;
> const int inf = 0x3f3f3f3f;
> struct node {
>  int id,priority;
> };
> struct SplayTree{
> 	int sz[maxn];
> 	int ch[maxn][2];
> 	int pre[maxn];
> 	int root , top1 , top2;
> 	int ss[maxn] , que[maxn];
> 	inline void Rotate(int x,int f) {
> 		int y = pre[x];
> 		ch[y][!f] = ch[x][f];
> 		pre[ ch[x][f] ] = y;
> 		pre[x] = pre[y];
> 		if(pre[x]) ch[ pre[y] ][ ch[pre[y]][1] == y ] = x;
> 		ch[x][f] = y;
> 		pre[y] = x;
> 		push_up(y);
> 	}
> 	inline void Splay(int x,int goal) {
> 		while(pre[x] != goal) {
> 			if(pre[pre[x]] == goal) {
> 				Rotate(x , ch[pre[x]][0] == x);
> 			} else {
> 				int y = pre[x] , z = pre[y];
> 				int f = (ch[z][0] == y);
> 				if(ch[y][f] == x) {
> 					Rotate(x , !f) , Rotate(x , f);
> 				} else {
> 					Rotate(y , f) , Rotate(x , f);
> 				}
> 			}
> 		}
> 		push_up(x);
> 		if(goal == 0) root = x;
> 	}
> 	inline void RotateTo(int k,int goal) {
> 		int x = root;
> 		while(sz[ ch[x][0] ] != k) {
> 			if(k < sz[ ch[x][0] ]) {
> 				x = ch[x][0];
> 			} else {
> 				k -= (sz[ ch[x][0] ] + 1);
> 				x = ch[x][1];
> 			}
> 		}
> 		Splay(x,goal);
> 	}
> 	inline void erase(int x) {
> 		int father = pre[x];
> 		int head = 0 , tail = 0;
> 		for (que[tail++] = x ; head < tail ; head ++) {
> 			ss[top2 ++] = que[head];
> 			if(ch[ que[head] ][0]) que[tail++] = ch[ que[head] ][0];
> 			if(ch[ que[head] ][1]) que[tail++] = ch[ que[head] ][1];
> 		}
> 		ch[ father ][ ch[father][1] == x ] = 0;
> 		push_up(father);
> 	}
> 	int NewNode(node c) {
>         int x;
> 		if (top2) x = ss[--top2];
> 		else x = ++top1;
> 		ch[x][0] = ch[x][1] = pre[x] = 0;
> 		sz[x] = 1;    client[x] = c;
>         return x;
> 	}
> 	inline void push_up(int x) {
> 		sz[x] = 1 + sz[ ch[x][0] ] + sz[ ch[x][1] ];
> 	}
> 
> 	inline void init() {
> 		ch[0][0] = ch[0][1] = pre[0] = sz[0] = 0;
> 		root = top1 = 0;
> 		node c;
> 		c.priority = -inf;
> 		c.id= 0;
> 		int x = NewNode(c);
> 		root=1;
> 		c.priority = inf;
> 		x = NewNode(c);
> 		pre[x] = root;
> 		ch[root][1]=x;
> 		sz[root] = 2;
>         num = 0;
> 		push_up(ch[root][1]);
> 		push_up(root);
> 	}
>     int Insert(int rt,node c) {
>      if(c.priority<client[rt].priority) {
>         if(ch[rt][0]) {
>           return  Insert(ch[rt][0],c);
>         }  else {
>             int x = NewNode(c);
>             pre[x]=rt;   ch[rt][0]=x;
>             push_up(rt);
>             return x;
>         }
>      }
>      if(c.priority>client[rt].priority){
>         if(ch[rt][1]) return Insert( ch[rt][1] ,c);
>         else {
>             int x = NewNode(c);
>             pre[x] = rt;   ch[rt][1] = x;  push_up(rt);
>             return x;
>         }
>      }
>     }
>     int readIn(){
>      int op  ;
>      node c;   scanf("%d",&op);
>      if(op==0) return 0;
>      if(op==1)    {
>         scanf("%d%d",&c.id,&c.priority);
>         int xx=Insert(root,c);  Splay(xx,0);
>         num++;
>      }
>      if(op==2)  {
>         if(num>=1)  {
>         RotateTo(num-1,0);
>         RotateTo(num+1,root);
>         printf("%d\n",client[keyTree].id);
>         erase(keyTree);
>         num--;
>         } else puts("0"), root=1;
>      }
>      if(op==3)  {
>         if(num>=1)  {
>         RotateTo(0,0);  RotateTo(2,root);
>         printf("%d\n",client[keyTree].id);
>         erase(keyTree);
>         num--;
>         } else puts("0"),root=1;
>      }
>      return 1;
>     }
>     node client[maxn];
>     int num;
> }spt;
> int main() {
>     spt.init();
> 	while(spt.readIn());
> 	return 0;
> }