/*
9 2
1 1 9
1 2 3
1 1 4
2
1 1 2
1 2 5
2
2
1 2 1

4
3
5

----

8 5
1 2 1369
1 2 13
1 2 69
1 2 3
2
2
2
2
*/

#include <cstdio>
#include <vector>

using namespace std;

#define MAXN 200000
#define MAXM 200000

#define MIN 1
#define MAX 2

int tidx[MAXM+1];

struct heap_elem { int v,v1; heap_elem(); } EMPTY;
heap_elem :: heap_elem() { v=v1=0; }

struct heap
{
	vector<heap_elem> ar; int n,type;
	heap();
	void add(int,int);
	heap_elem top(); heap_elem pop();
	void change_val(int,int);
} mh[MAXM],towns;
heap :: heap() { ar.push_back(EMPTY); n=0; type=MIN; }
void heap :: add(int val, int val1=-1) //O(logN)
{
	ar.push_back(EMPTY); n++;
	int idx=n;
	if(type==MIN)
		while(idx>1 and ar[idx>>1].v > val) { ar[idx] = ar[idx>>1]; idx=idx>>1; }
	else //type=max
		while(idx>1 and ar[idx>>1].v < val) { ar[idx] = ar[idx>>1]; idx=idx>>1; }
	ar[idx].v=val; ar[idx].v1=val1;
}
heap_elem heap :: top() { if(n==0) return EMPTY; return ar[1]; }
heap_elem heap :: pop() //O(logN)
{
	heap_elem ret=ar[1], t=ar[n];
	int idx=1;
	ar.pop_back(); n--;
	bool cont=true;
	while(idx*2 <= n and cont)
	{
		if(type==MIN)
		{
			if((idx<<1)+1 <= n and ar[(idx<<1)+1].v<ar[idx<<1].v and ar[(idx<<1)+1].v<t.v) { ar[idx]=ar[(idx<<1)+1]; idx=(idx<<1)+1;}
			else if(ar[idx<<1].v<t.v) { ar[idx]=ar[idx<<1]; idx=idx<<1; }
			else cont=false; //break
		}
		else //type=MAX
		{
			if((idx<<1)+1 <= n and ar[(idx<<1)+1].v>ar[idx<<1].v and ar[(idx<<1)+1].v>t.v) { ar[idx]=ar[(idx<<1)+1]; idx=(idx<<1)+1;}
			else if(ar[idx<<1].v>t.v) { ar[idx]=ar[idx<<1]; idx=idx<<1; }
			else cont=false; //break
		}
	}
	ar[idx] = t;
	return ret;
}
void heap :: change_val( int idx, int val ) //O(logN)
{
	//this is ONLY for the town heap
	//ar[idx].v = val;
	heap_elem t=ar[idx]; t.v=val;
	bool cont=true;
	while(idx*2 <= n and cont)
	{
		if(type==MIN)
		{
			if((idx<<1)+1 <= n and ar[(idx<<1)+1].v<ar[idx<<1].v and ar[(idx<<1)+1].v<val) { ar[idx]=ar[(idx<<1)+1]; tidx[ar[idx].v1]=idx; idx=(idx<<1)+1;}
			else if(ar[idx<<1].v<val) { ar[idx]=ar[idx<<1]; tidx[ar[idx].v1]=idx; idx=idx<<1; }
			else cont=false; //break
		}
		else //type=MAX
		{
			if((idx<<1)+1 <= n and ar[(idx<<1)+1].v>ar[idx<<1].v and ar[(idx<<1)+1].v>val) { ar[idx]=ar[(idx<<1)+1]; tidx[ar[idx].v1]=idx; idx=(idx<<1)+1;}
			else if(ar[idx<<1].v>val) { ar[idx]=ar[idx<<1]; tidx[ar[idx].v1]=idx; idx=idx<<1; }
			else cont=false; //break
		}
	}
	ar[idx]=t; tidx[ar[idx].v1]=idx;
}

//-------------------------------------------------

//N-events M-towns

int N,M;
void init()
{
	scanf("%d %d", &N,&M);
	towns.type = MAX;
	for(int i=1; i<=M; i++) towns.add(0,i);
	for(int i=1; i<=M; i++) tidx[towns.ar[i].v1]=i;
}


void solve()
{
	int a,b,c;
	heap_elem t;
	for(int i=0; i<N; i++)
	{
		scanf("%d", &a);
		if(a==1)
		{
			scanf("%d %d", &b, &c);
			mh[b].add(c);
			towns.change_val(tidx[b], mh[b].top().v);
			//printf("-%d\n", mh[b].top().v);
		}
		else
		{
			b=towns.top().v1; //the town that shall be the chosen one
			//printf("->%d\n", b);
			printf("%d\n", mh[b].pop().v);
			towns.change_val(1, mh[b].top().v);
		}
	}
}

int main()
{
	init();
	solve();
	return 0;
}
