G. Приоритетная очередь

Реализуйте кучей приоритетную очередь с двумя операциями: добавить элемент и извлечь максимум. Вместимость очереди ограничена числом $N$.

В этой задаче элементы могут повторяться, и поэтому нужны правила, делающие ответ однозначным:

1. Просеивание не двигает элемент дальше, чем нужно. Если $A[i] = A[2i]$, вызов просеивания не должен менять их местами: обмен равных кучу не портит, но он бесполезен.
2. При двух равных детях выбирается левый.

Первое правило означает строгое сравнение: a[i] > a[i / 2], а не >=. Второе - что при равенстве левого и правого ребёнка берётся левый, то есть проверка правого должна быть строгой относительно уже выбранного.

В первой строке - вместимость $N$ и число запросов $M$ ($1 \le N, M \le 10^5$).

Далее $M$ строк. Запрос типа 1 - извлечь максимум, без параметров. Запрос типа 2 - добавить число из $[-10^9; 10^9]$.

Ответ на каждый запрос по правилам выше, по одной строке.

После всех запросов - строка с кучей в конечном состоянии. Если очередь пуста, выведите пустую строку.