#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,t,p,k,tree[1<<19],ind[1<<19],st;
priority_queue<int> q[200001];
void update(int pos, int num)
{
	pos+=st;
	tree[pos]=num;
	pos/=2;
	while(pos>0)
	{
		if(tree[pos*2]>tree[pos*2+1]) ind[pos]=ind[pos*2];
		else ind[pos]=ind[pos*2+1];
		tree[pos]=max(tree[pos*2],tree[pos*2+1]);
		pos/=2;
	}
}
int query()
{
	return ind[1];
}
int main()
{
	scanf("%d%d",&n,&m);
	st=1;
	while(st<m) st*=2;
	st--;
	//st/=2;
	for(int i=1+st; i<=m+st; i++)
	{
		ind[i]=i-st;
	}
	for(int i=1; i<=n; i++)
	{
		scanf("%d",&t);
		if(t==1)
		{
			scanf("%d%d",&p,&k);
			if(q[p].empty()||k<-q[p].top()) update(p,k);
			q[p].push(-k);
		}
		else
		{
			/*int max1=0,maxp=0;
			for(int j=1; j<=m; j++)
			{
				if(max1<-q[j].top()) {max1=-q[j].top(); maxp=j;}
			}*/
			int maxp=query();
			printf("%d\n",-q[maxp].top());
			q[maxp].pop();
			update(maxp,(q[maxp].empty()?0:-q[maxp].top()));
		}
	}
	return 0;
}
