Problems
Очередь с приоритетами
Очередь с приоритетами
Реализуйте структуру "очередь с приоритетами", поддерживающую следующие операции:
\begin{enumerate}
\item Добавление элемента в очередь.
\item Удаление из очереди элемента с наибольшим приоритетом.
\item Изменение приоритета для произвольного элемента, находящегося в очереди.
\end{enumerate}
\InputFile
Программа получает на вход последовательность команд, по одной команде в каждой строке. Общее число команд не превосходит \textbf{30000}. Команда может иметь один из следующих форматов:
\begin{itemize}
\item \textbf{ADD id priority} - добавить в очередь новый элемент с идентификатором \textbf{id} и приоритетом \textbf{priority}. Гарантируется, что в очереди нет элемента с таким идентификатором.
\item \textbf{POP} - удалить из очереди элемент с наибольшим значением приоритета. Если таких элементов несколько, то удаляется один (любой) из них. Гарантируется, что очередь не пуста.
\item \textbf{CHANGE id new_priority} - изменить значение приоритета элемента с идентификатором \textbf{id} на значение \textbf{new_priority}. Гарантируется, что в очереди есть элемент с таким идентификатором.
\end{itemize}
Идентификаторы элементов - строки, состоящие из строчных латинских букв не более \textbf{10} символов. Идентификаторы - произвольные целые числа.
В самом начале очередь пуста.
\OutputFile
Для каждой команды типа \textbf{POP} выведите идентификатор удалённого элемента, и, через пробел, значение его приоритета.
Input example #1
ADD one 1 ADD two 2 ADD three 3 POP CHANGE one 5 POP POP
Output example #1
three 3 one 5 two 2