#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

int n, m;
const int MAXN = 200000 + 5;
priority_queue<int> q[MAXN];

struct itree { int val, nom; };
itree it[1 << 20];

itree MAX(itree a, itree b) {
    if(a.val > b.val) return a;
    return b;
    }

int t, w;
void update(int l, int r, int v) {
    if(l == r) {
            it[v].val = w, it[v].nom = t;
            return;
            }

    int mid = (l + r) >> 1;
    if(t <= mid) update(l, mid, v << 1);
    else update(mid + 1, r, (v << 1) + 1);
    it[v] = MAX(it[v << 1], it[(v << 1) + 1]);
    }

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

    int N = 1;
    while(N < n) N <<= 1;

    while(m--) {
        scanf("%d", &cmd);
        if(cmd == 1)
                scanf("%d%d", &t, &w),
                q[t].push(-w),
                w = -q[t].top(),
                update(1, N, 1);
        else {
            printf("%d\n", it[1].val),
            t = it[1].nom,
            q[t].pop();
            if(q[t].empty()) w = 0, update(1, N, 1);
            else w = -q[t].top(), update(1, N, 1);
            }
        }

    return 0;
    }
