#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] << " "; // Вывод кучи
}