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

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

int dp[1 << 22];

std::priority_queue<int, std::vector<int>, cmp> que[1 << 18];
void update(int cities, int city) {
    int logn = 1;
    while (logn < cities) logn <<= 1;
    int startIndex = logn + city;
    while (startIndex > 1) {
        startIndex >>= 1;
        if (que[dp[startIndex * 2]].top() > que[dp[startIndex * 2 + 1]].top()) {
            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; i++) dp[i + logn] = i;
    for (int i = 0;i < cities; i++) que[i].push(1000000000);

    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);
            if (inited) update(cities, city);
        }
        if (code == 2) {
            if (!inited) {
                inited = true;
                for (int i = 0;i < cities; ++i)
                    update(cities, i);
            }
            int minIndex = dp[1];
            std::cout << que[minIndex].top() << '\n';
            que[minIndex].pop();
            update(cities, minIndex);
        }
    }
    return 0;
}
