#include <iostream>
#include <stdio.h>
#include <queue>

#define mp make_pair

using namespace std;

typedef pair<int, int> PII;

const int MAXM = 200000 + 5;

int n, m;
priority_queue<int> pq[MAXM];
PII tree[1 << 19];
int cmd, t, w, city, lvs;

PII mergeNodes(PII le, PII ri) {
    if(le.first > ri.first) return le;
    return ri;
}

void update(int idx, int value) {
    idx += lvs;
    tree[idx] = mp(value, idx - lvs);
    idx >>= 1;
    while(idx) {
        tree[idx] = mergeNodes(tree[idx << 1], tree[(idx << 1) + 1]);
        idx >>= 1;
    }
}

int main()
{
    scanf("%d %d", &n, &m);

    lvs = 1;
    while(lvs < m) lvs <<= 1;

    for(int i = 1; i < 2 * lvs; i ++)
        tree[i] = mp(0, -1);

    for(int i = 0; i < n; i ++) {
        scanf("%d", &cmd);
        if(cmd == 2) {
            city = tree[1].second;
            printf("%d\n", -pq[city].top());
            pq[city].pop();
            if(!pq[city].empty()) update(city, -pq[city].top());
        }
        else {
            scanf("%d %d", &t, &w);
            t --;
            pq[t].push(-w);
            update(t, -pq[t].top());
        }
    }

    return 0;
}
