#include <iostream>
#include <vector>
// Я очень долго бился над этой задачей,
// она много раз не сдавалась, так что в конце
// в комментариях меня немного понесло,
// но их суть точно должна быть понятна.
// У меня будет 2 вида подмассивов - подмассив в куче
struct subArrayHeap;
// И его копия в двусвязном списке
struct subArrayList;
struct subArrayHeap {
    // Всюду далее:
    // l - левая граница подмассива,
    // r - правая граница подмассива,
    // левая и правая границы - обе включаются
    long long l, r;
    // Индекс подмассива в массиве,
    // на котором реализована куча:
    long long inx;
    // Указатель на копию в двусвязном списке:
    subArrayList* same_List;
    subArrayHeap(long long new_l, long long new_r) {
        l = new_l;
        r = new_r;
        inx = -1;
        same_List = nullptr;
    }
    // Вычисляет длину подмассива
    long long length() {
        return this->r - this->l + 1;
    }
    // Перегрузка оператора >:
    bool operator > (subArrayHeap *B) {
        return (this->length() > B->length() || (this->length() == B->length() && this->l < B->l));
    }
};

// Для удобства, функция Max возвращает наибольший
// подмассив из двух подмассивов, возможно благодаря перегрузке >
subArrayHeap* Max(subArrayHeap* A, subArrayHeap* B) {
    if (*A > B) {
        return A;
    } else {
        return B;
    }
}

// Структура, опрерирующая с двусвязным списком:
struct subArrayList {
    long long l, r;
    // Копия этого элемента в куче, если он свободен:
    subArrayHeap* same_Heap;
    // Указатель на подмассив, находящийся слева от данного:
    subArrayList* Left;
    // Указатель на подмассив, находящийся справа от данного
    subArrayList* Right;
    // Свободен или занят
    bool empty;
    subArrayList(long long new_l, long long new_r) {
        l = new_l;
        r = new_r;
        Left = nullptr;
        Right = nullptr;
        same_Heap = nullptr;
        empty = true;
    }
    // Аккуратное переписывание указателей,
    // если решаем удалить подмассив насовсем из списка:
    void kill() {
        // Возможно переписать, только если слева что - то есть
        if (this->Left) {
            this->Left->Right = this->Right;
        }
        if (this->Right) {
            this->Right->Left = this->Left;
        }
        delete this;
    }
};

// Делаем так, чтобы копия в 2-списке не указывала
// на уничтоженный элемент кучи
void killHeap(subArrayHeap* A) {
    A->same_List->same_Heap = nullptr;
    delete A;
}

// Реализация кучи, где на макушке максимальный:
struct Heap {
    // Вектор, на котором она будет сидеть:
    std::vector<subArrayHeap*> heap;
    Heap() {
        this->heap.resize(0);
    }
    // Показывает, сколько элементов в куче
    long long sizeHeap() {
        return this->heap.size();
    }
    // Дает информацию о том, пуста ли куча:
    bool notEmpty() {
        if (this->sizeHeap() == 0) {
            return false;
        } else {
            return true;
        }
    }
    // Для удобства возвращает указатель на макушку кучи
    subArrayHeap* top() {
        return this->heap[0];
    }
    // Возвращает указатель на родителя
    subArrayHeap* Parent(subArrayHeap* A) {
        if (A->inx == 0) {
            return nullptr;
        } else {
            return heap[(A->inx - 1)/2];
        }
    }
    // Возвращает указатель на левого ребенка:
    subArrayHeap* LeftChild(subArrayHeap* A) {
        if (2*(A->inx) + 1 >= this->sizeHeap()) {
            return nullptr;
        } else {
            return this->heap[2*(A->inx) + 1];
        }
    }
    // Возвращает указатель на правого ребенка:
    subArrayHeap* RightChild(subArrayHeap* A) {
        if (2*(A->inx) + 2 >= this->sizeHeap()) {
            return nullptr;
        } else {
            return this->heap[2*(A->inx) + 2];
        }
    }
    // Меняет 2 элемента кучи, аккуратно обходясь с параметром inx:
    void SwapHeap(subArrayHeap* A, subArrayHeap* B) {
        subArrayHeap* x = A;
        long long inx_A = A->inx;
        this->heap[A->inx] = B;
        this->heap[B->inx] = x;
        A->inx = B->inx;
        B->inx = inx_A;
    }
    // Операция siftUp - обсуждалась на лекции
    void siftUp(subArrayHeap* A) {
        if (A->inx == 0) {
            return;
        }
        if (*Parent(A) > A) {
            return;
        } else {
            this->SwapHeap(A, this->Parent(A));
            this->siftUp(A);
        }
    }
    // Аналогично, обсуждалась на лекции
    void siftDown(subArrayHeap* A) {
        if (this->RightChild(A)) {
            if (*Max(this->LeftChild(A), this->RightChild(A)) > A) {
                SwapHeap(Max(this->LeftChild(A), this->RightChild(A)), A);
                siftDown(A);
            } else {
                return;
            }
        } else if (this->LeftChild(A)) {
            if (*this->LeftChild(A) > A) {
                SwapHeap(A, this->LeftChild(A));
                siftDown(A);
            } else {
                return;
            }
        }
    }
    // Чтобы удалить макушку, меняем его местами с последним элементом кучи,
    // удаляем элемент из памяти, попаем вектор и
    // получаем корректно построенную кучу
    void killTop() {
        SwapHeap(this->heap[0], this->heap[this->sizeHeap() - 1]);
        killHeap(this->heap[this->sizeHeap() - 1]);
        this->heap.pop_back();
        this->siftDown(this->heap[0]);
    }
    // Чтобы удалить произвольный элемент из кучи,
    // присваиваем ему космическую длину, siftUp
    // гарантированно поднимет его на макушку,
    // с помощью уже реализованного метода killTop():
    void killAny(subArrayHeap* A) {
        A->l = -1;
        A->r = 2147483650;
        this->siftUp(A);
        this->killTop();
    }
    // Добавляем элемент списка в кучу:
    void addHeap(subArrayList* B) {
        // Создаем новый подмассив (В КУЧЕ)
        auto* A = new subArrayHeap(B->l, B->r);
        // Элемент списка должен указывать на кучу
        B->same_Heap = A;
        // А элемент кучи, в свою очередь - на список
        A->same_List = B;
        // Коли мы его добавили в куче,
        // то он может быть пустым и никак иначе
        B->empty = true;
        // Кидаем его в кучу
        this->heap.push_back(A);
        // Говорим, что его индекс теперь самый правый
        A->inx = this->sizeHeap() - 1;
        // Поднимаем этот элементик:
        siftUp(A);
    }
};

// Для удобства реализуем структуру запроса
struct request {
    // Это запрос на выделение памяти?
    bool occupy;
    // Получилось выделить память?
    bool achieved;
    // А где тот подмассив, который мы заняли на этом запросе
    subArrayList* place;
    request() {
        this->occupy = false;
        this->achieved = false;
        this->place = nullptr;
    }
};

// Cтруктура менеджера:
struct Manager {
    // Даем ему в распоряжение кучу:
    Heap H;
    // N, M - из условий задачи
    long long N, M;
    // Менеджер памяти оперирует с запросами - логично держать его рядом
    std::vector<request> req;
    Manager(long long new_N, long long new_M) {
        this->N = new_N;
        this->M = new_M;
        // Запросы нумеруются с единицы,
        // так что пожертвуем ноликовым запросом - он никогда не будет использоваться
        this->req.resize(M + 1);
        // Создаем изначальный подмассив,
        // который говорит, что все место пока свободно
        auto* BIG = new subArrayList(1, N);
        // Кидаем его в кучу:
        this->H.addHeap(BIG);
    }
    // Выделение K памяти на r - том запросе
    long long occupy(long long K, long long r) {
        // Да, это запрос на выделение памяти
        this->req[r].occupy = true;
        if (this->H.notEmpty() && this->H.top()->length() >= K) {
            // Куча непуста, на макушке хватает места,
            // так что мы успешно выделили память
            this->req[r].achieved = true;
            // 1. На макушке ровно столько места, сколько нам сейчас надо:
            if (this->H.top()->length() == K) {
                // Для удобства,
                // обозначаем указатель на макушку новой переменной place
                subArrayList* place = this->H.top()->same_List;
                // Теперь вся макушка занята
                this->H.top()->same_List->empty = false;
                // А в куче теперь уже ничего нет, так что указатель пустой
                this->H.top()->same_List->same_Heap = nullptr;
                // Удаляем его из кучи:
                H.killTop();
                // Мы заняли макушку кучи, так что скажем,
                // что на r - том запросе был занят подмассив place
                this->req[r].place = place;
                // Выведем левую границу подмассива, что и просили в условии
                return place->l;
            // Если же вдруг надо занять не всю макушку:
            } else {
                // Новый свободный подмассивчик new_free откололся от макушки,
                // как напоминание о том, что когда - то здесь было свободно.
                // Ну и, конечно, что он все еще свободен и может понадобиться
                auto* new_free = new
                        subArrayList(this->H.top()->l + K, this->H.top()->r);
                // Урезаем макушку:
                this->H.top()->same_List->r = this->H.top()->same_List->l + K - 1;
                // Теперь макушка занята
                this->H.top()->same_List->empty = false;
                // Если справа от копии макушки в списке что - то есть,
                // то пусть он говорит, что слева от него теперь стоит new_free
                if (this->H.top()->same_List->Right) {
                    this->H.top()->same_List->Right->Left = new_free;
                    // А new_free скажет, что справа от него стоит тот, который стоял
                    // когда - то справа от копии макушки в списке макушки
                    new_free->Right = this->H.top()->same_List->Right;
                }
                // Теперь справа от копии макушки в списке стоит new_free
                this->H.top()->same_List->Right = new_free;
                // Слева от new_free теперь стоит копия макушки в списке
                new_free->Left = this->H.top()->same_List;
                // Теперь копия макушки в списке на кучу
                // даже смотреть не может после того, как стала занятой...
                this->H.top()->same_List->same_Heap = nullptr;
                // Теперь новый свободный подмассивчик new_free говорит макушке,
                // что он - все, что от нее осталось
                new_free->same_Heap = H.top();
                // Макушка соглашается с этим и говорит,
                // что new_free и она это одно и то же
                this->H.top()->same_List = new_free;
                // И стыдливо уменьшает свою длину до уровня new_free:
                this->H.top()->l = new_free->l;
                this->H.top()->r = new_free->r;
                // Теперь она стала меньше, и, возможно,
                // она теперь не самый большой свободный подмассивчик в куче.
                // Она жертвует своим высоким положением
                // и цена этой жертвы - корректно построенная куча.
                H.siftDown(this->H.top());
                // Теперь то, что стоит слева от
                // нового свободного подмассива - это то, что мы заняли
                this->req[r].place = new_free->Left;
                // Выводим то, что и хотят в задаче:
                return new_free->Left->l;
            }
        // Выделить память не получилось, так что выводим -1,
        // параметры менять не надо в силу того, как определен конструктор
        // в структуре запроса
        } else {
            return -1;
        }
    }
    // Освобождение r - того запроса:
    void release(long long r) {
        // Получилось ли выделить память на r - том запросе?
        if (this->req[r].achieved) {
            // Также берем указатель на освобождаемый подмассив
            // за новую переменную для удобства обращения:
            subArrayList* place = this->req[r].place;
            // 1. Слева и справа есть свободные подмассивы
            if (place->Left && place->Right &&
            place->Left->empty && place->Right->empty) {
                // Сохраняем указатель на то,
                // что стоит слева от освобождаемого в 2-списке:
                subArrayList* placeLeft = place->Left;
                // Растягиваем левый до уровня правого:
                place->Left->r = place->Right->r;
                // Удаляем в куче правый так как правый свободен:
                this->H.killAny(place->Right->same_Heap);
                // Удаляем правый в списке:
                place->Right->kill();
                // Удаляем освобождаемый в списке:
                place->kill();
                // Растягиваем левый и в куче тоже
                placeLeft->same_Heap->r = placeLeft->r;
                // Он стал больше, так что поднимем его в куче,
                // чтобы получить корректно построенную кучу:
                this->H.siftUp(placeLeft->same_Heap);
            // 2. Cлева либо занято, либо ничего нет, справа свободный подмассив:
            } else if (place->Right && place->Right->empty) {
                // Растягиваем то, что справа влево до уровня освобождаемого
                // (мы же их типа здесь сливаем)
                place->Right->l = place->l;
                // Изменяем и в куче тоже:
                place->Right->same_Heap->l = place->Right->l;
                // Он стал больше в куче, так что поднимаем его,
                // чтобы получить корректно построенную кучу:
                this->H.siftUp(place->Right->same_Heap);
                // Теперь тот, что был освобождаемый, стал ненужен,
                // так как его поглотил правый, можем его с чистой совестью уничтожить
                place->kill();
            // 3. Справа либо ничего нет, либо занято, слева свободный подмассив:
            } else if (place->Left && place->Left->empty) {
                // Ничем не отличается от предыдущего случаа,
                // то что происходит в 2. и 3. - суть одно и то же
                place->Left->r = place->r;
                place->Left->same_Heap->r = place->Left->r;
                this->H.siftUp(place->Left->same_Heap);
                place->kill();
            // 4. Слева и справа либо ничего нет, либо занятые подмассивы:
            } else {
                // Сливать теперь ничего не надо, так что просто говорим,
                // что освобождаемый подмассивчик таки свободен и закидываем его в кучу
                place->empty = true;
                H.addHeap(place);
            }
        }
    }
    // Реализованный для удобства метод чтобы обработать один запрос:
    void Process_One_Request(long long T, long long r) {
        // По условию, если поступает положительное число,
        // то это запрос на выделение памяти
        if (T > 0) {
            std::cout << this->occupy(T, r) << std::endl;
        // Если же отрицательное, то освобождение
        } else {
            this->release(-T);
        }
    }
    // Также для удобства, но тут уже обрабатываются все M запросов:
    void Process_All_Requests() {
        for (int i = 1; i < M + 1; ++i) {
            long long T;
            std::cin >> T;
            Process_One_Request(T, i);
        }
    }
};

int main() {
    long long N, M;
    std::cin >> N >> M;
    Manager Man(N, M);
    Man.Process_All_Requests();
}