Priority Queue

Input

The program will receive a sequence of commands as input, with one command per line. The total number of commands will not exceed $30000$. Each command can be in one of the following formats:

• ADD id priority — Add a new element to the queue with the identifier id and priority priority. It is guaranteed that no element with this identifier currently exists in the queue.

• POP — Remove the element with the highest priority from the queue. If there are multiple elements with the same highest priority, remove any one of them. It is guaranteed that the queue is not empty.

• CHANGE id new_priority — Change the priority of the element with the identifier id to new_priority. It is guaranteed that an element with this identifier exists in the queue.

Element identifiers are strings composed of lowercase Latin letters, with a maximum length of $10$ characters. Priorities are arbitrary integers.

Initially, the queue is empty.

Output

For each POP command, output the identifier of the removed element, followed by a space, and then its priority value.

Esempi