#include <bits/stdc++.h>
 
using namespace std;
 
const long max_size = 100000;
long long heap[max_size];
long h_size = 0; // Текущий размер кучи
 
void sift_down(long i, bool f = true) { // f - нужно ли выводить конечную позицию элемента или нет
    while (i * 2 + 1 < h_size) {
        long j = i * 2 + 1;
        if (j + 1 < h_size && heap[j + 1] > heap[j]) ++j;
        if (heap[i] < heap[j]) swap(heap[i], heap[j]);
        else break;
        i = j;
    }
    if (f) cout << i + 1 << " "; // Вывод конечной позиции элемента
}
 
void sift_up(long i, bool f = true) { // f - нужно ли выводить конечную позицию элемента или нет
    while (heap[i] > heap[(i - 1) / 2]) {
        swap(heap[i], heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
    if (f) cout << i + 1 << endl; // Вывод конечной позиции элемента
}
 
int main() {
    ios_base::sync_with_stdio(false);
    long n, m;
    cin >> n >> m; // n максимальный размер кучи, m количество заросов
    for (long i = 0; i < m; i++) {
        long a;
        cin >> a; // Тип запроса, 1, 2 или 3
        if (a == 1) { // Тут все правильно
            if (!h_size) cout << -1 << "\n";
            else {
                long x = heap[0];
                heap[0] = heap[--h_size];
                if (!h_size) cout << "0 ";
                else sift_down(0);
                cout << x << "\n";
            }
        }
        if (a == 2) {  // Тут все правильно
            long long b;
            cin >> b;
            if (h_size == n) cout << "-1\n";
            else {
                heap[h_size++] = b;
                sift_up(h_size - 1);
            }
        }
        if (a == 3) { // Вот тут по идее проблемы
            long b; // Индекс удаляемого элемента
            cin >> b;
            if (h_size < b) cout << "-1\n";
            else {
                long long x = heap[--b];
                cout << x << "\n"; // Выводим сам элемент
                heap[b] = heap[--h_size]; // Ставим на его место последний
                sift_up(b, false); // По условию выводить конечную позицию элемента 
                sift_down(b, false); // не нужно когда запрос типа 3, потому false
            }
        }
    }
    for (long i = 0; i < h_size; i++) cout << heap[i] << " "; // Вывод кучи
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgbG9uZyBtYXhfc2l6ZSA9IDEwMDAwMDsKbG9uZyBsb25nIGhlYXBbbWF4X3NpemVdOwpsb25nIGhfc2l6ZSA9IDA7IC8vINCi0LXQutGD0YnQuNC5INGA0LDQt9C80LXRgCDQutGD0YfQuAoKdm9pZCBzaWZ0X2Rvd24obG9uZyBpLCBib29sIGYgPSB0cnVlKSB7IC8vIGYgLSDQvdGD0LbQvdC+INC70Lgg0LLRi9Cy0L7QtNC40YLRjCDQutC+0L3QtdGH0L3Rg9GOINC/0L7Qt9C40YbQuNGOINGN0LvQtdC80LXQvdGC0LAg0LjQu9C4INC90LXRggogICAgd2hpbGUgKGkgKiAyICsgMSA8IGhfc2l6ZSkgewogICAgICAgIGxvbmcgaiA9IGkgKiAyICsgMTsKICAgICAgICBpZiAoaiArIDEgPCBoX3NpemUgJiYgaGVhcFtqICsgMV0gPiBoZWFwW2pdKSArK2o7CiAgICAgICAgaWYgKGhlYXBbaV0gPCBoZWFwW2pdKSBzd2FwKGhlYXBbaV0sIGhlYXBbal0pOwogICAgICAgIGVsc2UgYnJlYWs7CiAgICAgICAgaSA9IGo7CiAgICB9CiAgICBpZiAoZikgY291dCA8PCBpICsgMSA8PCAiICI7IC8vINCS0YvQstC+0LQg0LrQvtC90LXRh9C90L7QuSDQv9C+0LfQuNGG0LjQuCDRjdC70LXQvNC10L3RgtCwCn0KCnZvaWQgc2lmdF91cChsb25nIGksIGJvb2wgZiA9IHRydWUpIHsgLy8gZiAtINC90YPQttC90L4g0LvQuCDQstGL0LLQvtC00LjRgtGMINC60L7QvdC10YfQvdGD0Y4g0L/QvtC30LjRhtC40Y4g0Y3Qu9C10LzQtdC90YLQsCDQuNC70Lgg0L3QtdGCCiAgICB3aGlsZSAoaGVhcFtpXSA+IGhlYXBbKGkgLSAxKSAvIDJdKSB7CiAgICAgICAgc3dhcChoZWFwW2ldLCBoZWFwWyhpIC0gMSkgLyAyXSk7CiAgICAgICAgaSA9IChpIC0gMSkgLyAyOwogICAgfQogICAgaWYgKGYpIGNvdXQgPDwgaSArIDEgPDwgZW5kbDsgLy8g0JLRi9Cy0L7QtCDQutC+0L3QtdGH0L3QvtC5INC/0L7Qt9C40YbQuNC4INGN0LvQtdC80LXQvdGC0LAKfQoKaW50IG1haW4oKSB7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGxvbmcgbiwgbTsKICAgIGNpbiA+PiBuID4+IG07IC8vIG4g0LzQsNC60YHQuNC80LDQu9GM0L3Ri9C5INGA0LDQt9C80LXRgCDQutGD0YfQuCwgbSDQutC+0LvQuNGH0LXRgdGC0LLQviDQt9Cw0YDQvtGB0L7QsgogICAgZm9yIChsb25nIGkgPSAwOyBpIDwgbTsgaSsrKSB7CiAgICAgICAgbG9uZyBhOwogICAgICAgIGNpbiA+PiBhOyAvLyDQotC40L8g0LfQsNC/0YDQvtGB0LAsIDEsIDIg0LjQu9C4IDMKICAgICAgICBpZiAoYSA9PSAxKSB7IC8vINCi0YPRgiDQstGB0LUg0L/RgNCw0LLQuNC70YzQvdC+CiAgICAgICAgICAgIGlmICghaF9zaXplKSBjb3V0IDw8IC0xIDw8ICJcbiI7CiAgICAgICAgICAgIGVsc2UgewogICAgICAgICAgICAgICAgbG9uZyB4ID0gaGVhcFswXTsKICAgICAgICAgICAgICAgIGhlYXBbMF0gPSBoZWFwWy0taF9zaXplXTsKICAgICAgICAgICAgICAgIGlmICghaF9zaXplKSBjb3V0IDw8ICIwICI7CiAgICAgICAgICAgICAgICBlbHNlIHNpZnRfZG93bigwKTsKICAgICAgICAgICAgICAgIGNvdXQgPDwgeCA8PCAiXG4iOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGlmIChhID09IDIpIHsgIC8vINCi0YPRgiDQstGB0LUg0L/RgNCw0LLQuNC70YzQvdC+CiAgICAgICAgICAgIGxvbmcgbG9uZyBiOwogICAgICAgICAgICBjaW4gPj4gYjsKICAgICAgICAgICAgaWYgKGhfc2l6ZSA9PSBuKSBjb3V0IDw8ICItMVxuIjsKICAgICAgICAgICAgZWxzZSB7CiAgICAgICAgICAgICAgICBoZWFwW2hfc2l6ZSsrXSA9IGI7CiAgICAgICAgICAgICAgICBzaWZ0X3VwKGhfc2l6ZSAtIDEpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGlmIChhID09IDMpIHsgLy8g0JLQvtGCINGC0YPRgiDQv9C+INC40LTQtdC1INC/0YDQvtCx0LvQtdC80YsKICAgICAgICAgICAgbG9uZyBiOyAvLyDQmNC90LTQtdC60YEg0YPQtNCw0LvRj9C10LzQvtCz0L4g0Y3Qu9C10LzQtdC90YLQsAogICAgICAgICAgICBjaW4gPj4gYjsKICAgICAgICAgICAgaWYgKGhfc2l6ZSA8IGIpIGNvdXQgPDwgIi0xXG4iOwogICAgICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAgIGxvbmcgbG9uZyB4ID0gaGVhcFstLWJdOwogICAgICAgICAgICAgICAgY291dCA8PCB4IDw8ICJcbiI7IC8vINCS0YvQstC+0LTQuNC8INGB0LDQvCDRjdC70LXQvNC10L3RggogICAgICAgICAgICAgICAgaGVhcFtiXSA9IGhlYXBbLS1oX3NpemVdOyAvLyDQodGC0LDQstC40Lwg0L3QsCDQtdCz0L4g0LzQtdGB0YLQviDQv9C+0YHQu9C10LTQvdC40LkKICAgICAgICAgICAgICAgIHNpZnRfdXAoYiwgZmFsc2UpOyAvLyDQn9C+INGD0YHQu9C+0LLQuNGOINCy0YvQstC+0LTQuNGC0Ywg0LrQvtC90LXRh9C90YPRjiDQv9C+0LfQuNGG0LjRjiDRjdC70LXQvNC10L3RgtCwIAogICAgICAgICAgICAgICAgc2lmdF9kb3duKGIsIGZhbHNlKTsgLy8g0L3QtSDQvdGD0LbQvdC+INC60L7Qs9C00LAg0LfQsNC/0YDQvtGBINGC0LjQv9CwIDMsINC/0L7RgtC+0LzRgyBmYWxzZQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgZm9yIChsb25nIGkgPSAwOyBpIDwgaF9zaXplOyBpKyspIGNvdXQgPDwgaGVhcFtpXSA8PCAiICI7IC8vINCS0YvQstC+0LQg0LrRg9GH0LgKfQo=

NCAxMAoxCjIgOQoyIDQKMiA5CjIgOQoyIDcKMQozIDQKMiAxCjMgMw==

4 10
1
2 9
2 4
2 9
2 9
2 7
1
3 4
2 1
3 3