Message Priority Queue

You are given a series of operations to perform on a Message Priority Queue.

This queue supports two operations:

• INSERT priority message: Insert a message with the given integer priority. The message is a single word.
• RETRIEVE: Retrieve and remove the message with the highest priority. If multiple messages have the same priority, retrieve the one that was inserted first.

If a RETRIEVE operation is performed when the queue is empty, output None.

For example, if you perform the following operations:

INSERT 5 hello
INSERT 3 world
INSERT 4 example
RETRIEVE
RETRIEVE
RETRIEVE

Then the output should be:

hello
example
world

The queue behavior can be summarized by the formula below (using LaTeX for clarity):

\( out = \begin{cases} message, & \text{if the queue is not empty} \\ None, & \text{if the queue is empty} \end{cases} \)

inputFormat

The input begins with an integer n (\(n \ge 1\)) representing the number of operations. The following n lines each contain a single operation. Each operation is either:

• INSERT priority message where priority is an integer and message is a word without spaces.
• RETRIEVE

The operations are provided via stdin.

outputFormat

For each RETRIEVE operation, output the retrieved message on a new line via stdout. If the queue is empty at the time of a RETRIEVE operation, output None (without quotes).

## sample

2
INSERT 5 hello
RETRIEVE

hello

</p>