H. Приоритетная очередь с удалением

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

Правила разрешения неоднозначности те же.

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

Далее $M$ строк. Тип 1 - извлечь максимум. Тип 2 - добавить число из $[-10^9; 10^9]$. Тип 3 - удалить элемент с данным индексом $i$.

На запросы типов 1 и 2 - как в предыдущей задаче.

На запрос типа 3 - значение удалённого элемента или $-1$, если элемента с таким индексом нет.

После всех запросов - строка с кучей в конечном состоянии.