有一个队列，队列里的每一个元素都是由(标号，优先级) 构成的

多组输入，每行输入一个op
如果op为1，要求插入一个数，格式为{编号，优先级}

如果op为2，输出优先级最大的元素并删除

如果op为3，输出优先级最小的元素并删除

如果op为0，结束

现在没法提交，要求不恶搞能调过样例就行

输入


2
1 20 14
1 30 3
2
1 10 99
3
2
2
0

输出
0
20
30
10

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;
struct node
{
	int l,r,c,p,rd,sz;
};
node fhq[N];
int tot=0,rt=0;

void upd(int x)
{
	fhq[x].sz=fhq[fhq[x].l].sz+fhq[fhq[x].r].sz+1;
}
void split(int rt,int x,int y,int p)
{
	if(rt==0)
	{
		x=0,y=0;return;
	}
	if(fhq[rt].c<=p)
	{
		x=rt;split(fhq[rt].r,fhq[x].r,y,p);
	}
	else
	{
		y=rt;split(fhq[rt].l,x,fhq[y].l,p);
	}
	upd(rt);
} 
int merge(int x,int y)
{
	if(x==0 || y==0) return x+y;
	if(fhq[x].rd>fhq[y].rd)
	{
		fhq[x].r=merge(fhq[x].r,y);
		upd(x);
		return x;
	}
	else
	{
		fhq[y].l=merge(x,fhq[y].l);
		upd(y);
		return y;
	}
}
void insert(int k,int p)
{
	int x,y;
    split(rt,x,y,p);tot++;
	fhq[tot].c=p;fhq[tot].p=k;fhq[tot].rd=rand();fhq[tot].sz=1;
    int id=tot;
    
	rt=merge(merge(x,id),y);
}
int kth(int rt,int pai)
{
//	cout<<rt<<endl;
	if(fhq[fhq[rt].l].sz+1==pai) return fhq[rt].p;
	if(fhq[fhq[rt].l].sz>=pai) return kth(fhq[rt].l,pai);
	else return kth(fhq[rt].r,pai-(fhq[fhq[rt].l].sz+1));
}
int kkth(int rt,int pai)
{
	if(fhq[fhq[rt].l].sz+1==pai) return fhq[rt].c;
	if(fhq[fhq[rt].l].sz>=pai) return kkth(fhq[rt].l,pai);
	else return kkth(fhq[rt].r,pai-(fhq[fhq[rt].l].sz+1));
}
void del(int v)
{
	int x,y,id;
	split(rt,x,y,v);
	split(x,x,id,v-1);
	rt=merge(x,y);
}
int main()
{
	int op;
	while(scanf("%d",&op)==1)
	{
        int k,p;
        //cout<<rt<<"asdf"<<endl;
		if(op==0) break;
		if(op==1)
		{
			scanf("%d%d",&k,&p);
			insert(k,p);
		}
		else if(op==2)
		{
			if(fhq[rt].sz==0)
			{
				puts("0");
				continue;
			}
			printf("%d\n",kth(rt,1));
			del(kkth(rt,1));
		}
		else
		{
			if(fhq[rt].sz==0)
			{
				puts("0");
				continue;
			}
			printf("%d\n",kth(rt,fhq[rt].sz));
			del(kkth(rt,fhq[rt].sz));
		}
	}
}
/* 
2
1 20 14
1 30 3
2
1 10 99
3
2
2
0
*/