#include <iostream>
#include <vector>
#include <queue>

struct cmp {
    bool operator()(int a, int b) {
        return a > b;
    }
};

struct rec {
    int index, w;
    rec(){}
    rec(int i, int x) { index = i; w = x; }
} dp[1 << 20];
bool operator>(rec a, rec b) {
    return a.w > b.w;
}
std::priority_queue<int, std::vector<int>, cmp> que[1 << 20];
void update(int cities, int city) {
    int logn = 1;
    while (logn < cities) logn <<= 1;
    dp[logn + city] = rec(city, que[city].top());
    int startIndex = logn + city;
    while (startIndex > 1) {
        startIndex >>= 1;
        if (dp[startIndex * 2] > dp[startIndex * 2 + 1]) {
            dp[startIndex] = dp[startIndex * 2];
        } else {
            dp[startIndex] = dp[startIndex * 2 + 1];
        }
    }
}

int main() {
    std::cin.tie(NULL);

    int queries, cities;
    std::cin >> queries >> cities;

    int logn = 1;
    while (logn < cities) logn <<= 1;

    bool inited = false;
    for (int i = 0;i < cities * 3; i++) dp[i + logn] = rec(i, 0);

    for (int i = 0;i < queries; ++i) {
        int code;
        std::cin >> code;
        if (code == 1) {
            int city, w;
            std::cin >> city >> w;
            city--;
            que[city].push(w);
            update(cities, city);
        }
        if (code == 2) {
            if (!inited) {
                inited = true;
                for (int i = 0;i < cities; ++i)
                    update(cities, i);
            }
            rec minIndex = dp[1];
            std::cout << que[minIndex.index].top() << '\n';
            que[minIndex.index].pop();
            update(cities, minIndex.index);
        }
    }
    return 0;
}
