#include <cstdio>
#include <algorithm>
#include <cassert>
using namespace std;

const int DMAX = 200005;
int H[DMAX], l, X, CR[DMAX], IN[DMAX];

void heap_insert () {

    int cnod = H[l], i = l;
    while (H[i / 2] > cnod && i != 1)
        H[i] = H[i / 2], swap (CR[IN[i]], CR[IN[i / 2]]), swap (IN[i], IN[i / 2]), i /= 2;
    H[i] = cnod;

}

void heap_eject (int nod) {

    int i = nod, cnod = H[nod]; bool k;
    while (H[i / 2] > cnod && i != 1)
        H[i] = H[i / 2], swap (CR[IN[i]], CR[IN[i / 2]]), swap (IN[i], IN[i / 2]), i /= 2;
    while (k = (H[i * 2] < H[i]) || H[i * 2 + 1] < H[i])
        if(k)
            H[i] = H[i * 2], swap (CR[IN[i]], CR[IN[i * 2]]), swap (IN[i], IN[i * 2]), i *= 2;
        else
            H[i] = H[i * 2 + 1], swap (CR[IN[i]], CR[IN[i * 2 + 1]]), swap (IN[i], IN[i * 2 + 1]), i = i * 2 + 1;
    H[i] = cnod;
}

int main() {

    freopen ("heapuri.in", "r", stdin); freopen ("heapuri.out", "w", stdout);
    int N, C = 0, i = 0, j;
    scanf ("%d%d", &N, &C);
    assert (1 <= N && N <= 200000);
    for (j = 1; j <= N; scanf("%d", &C), ++j)
        switch (C) {
        case 1:
            scanf ("%d", &X); assert(1 <= X && X <= 1000000000); H[++l] = X; CR[++i] = l; IN[l] = i; heap_insert(); break;
        case 2:
            scanf ("%d", &X); assert(1 <= X && X <= 1000000000); H[CR[X]] = H[l--]; heap_eject (CR[X]); break;
        default:
            printf ("%d\n", H[1]);
        }

}