#include <iostream>
using namespace std;

int parent (int index);
int leftChild (int index);
int rightChild (int index);
int siftDown (int *heap, int index, int size);
int siftUp (int *heap, int index);
void extractMax(int *heap, int size);
void addElement(int *heap, int currHeapSize, int newElement, const int heapSize);
void deleteElement(int *heap, int currHeapSize, int index);
enum operations {EXTRACT = 1, ADD, DELETE};
int currPyramidSize = 0;
int main () {
    int heapSize, numberOfOperations;
    int operationType;
    int newElement, deleteIndex;
    cin >> heapSize;
    cin >> numberOfOperations;
    int *heap = new int [heapSize];
    for (int count = 0; count < numberOfOperations; ++count) {
        cin >> operationType;
        if (operationType == operations::EXTRACT) {
            extractMax(heap, currPyramidSize);
        }
        else if (operationType == operations::ADD) {
            ++currPyramidSize;
            cin >> newElement;
            addElement(heap, currPyramidSize, newElement, heapSize);
        }
        else if (operationType == operations ::DELETE) {
            cin >> deleteIndex;
            deleteElement(heap, currPyramidSize, deleteIndex - 1);
        }
    }
    for (int i = 0; i < currPyramidSize; ++i) {
        cout << *(heap + i) << " ";
    }
    delete []heap;
}
int parent (int index) {
    return (index - 1) / 2;
}
int leftChild (int index) {
    return 2 * index + 1;
}
int rightChild (int index) {
    return 2 * index + 2;
}
int siftDown (int *heap, int index, int size) {
    while (leftChild(index) <= size - 1 && (heap[index] < heap[leftChild(index)] ||
    (heap[index] < heap[rightChild(index)] && rightChild(index) <= size - 1))) {
        int indexMax = (heap[rightChild(index)] > heap[leftChild(index)] && rightChild(index) <= size - 1) ? rightChild(index) : leftChild(index);
        swap(heap[index], heap[indexMax]);
        index = indexMax;
    }
    return index + 1;
}
int siftUp (int *heap, int index) {
    while (index > 0 && heap[index] > heap[parent(index)]) {
        swap(heap[index], heap[parent(index)]);
        index = parent(index);
    }
    return index + 1;
}
void extractMax(int *heap, int size) {
    if (size > 1) {
        swap(heap[0], heap[size - 1]);
        cout << siftDown(heap, 0, size - 1) << " ";
        cout << heap[size - 1] << endl;
        --currPyramidSize;
    }
    else if (size == 1) {
        cout << 0 << " ";
        cout << heap[size - 1] << endl;
        --currPyramidSize;
    }
    else if (size <= 0) {
        cout << -1 << endl;
    }
}
void addElement(int *heap, int currHeapSize, int newElement, const int heapSize) {
    if (currHeapSize <= heapSize) {
        heap[currHeapSize - 1] = newElement;
        cout << siftUp(heap, currHeapSize - 1) << endl;
    }
    else if (currHeapSize > heapSize) {
        cout << -1 << endl;
        --currPyramidSize;
    }
}
void deleteElement(int *heap, int currHeapSize, int index) {
    if (index >= 0 && index <= currHeapSize - 1) {
        cout << heap[index] << endl;
        swap(heap[index], heap[currHeapSize - 1]);
        siftDown(heap, index , currHeapSize - 1);
        siftUp(heap, index);
        --currPyramidSize;
    }
    else if (index < 0 || index > currHeapSize - 1) {
        cout << -1 << endl;
    }
}