Manager

A common paradigm in parallel processing is the producer/consumer paradigm, which can be implemented with a system consisting of one manager process and several client processes. The clients may be producers, consumers, and so on. The manager keeps track of the client processes. Each process is identified by its cost, a strictly positive integer with $1 \le \text{cost} \le 10000$. The number of processes sharing the same cost cannot exceed 10000. The manager maintains a queue and handles four kinds of requests:

• a x — add to the queue the process whose cost is $x$;
• r — remove one process from the queue, if possible, according to the current policy;
• p i — set the manager policy to $i$, where $i$ is 1 or 2 (the default policy is 1);
• e — end the list of requests.

There are two manager policies:

• policy 1 — remove the process of minimum cost;
• policy 2 — remove the process of maximum cost.

The manager prints the cost of a removed process only when the ordinal number of that remove request appears in the removal list.

Write a program that simulates the manager.

Each data set has the following format:

• the maximum cost of the processes;
• the length of the removal list;
• the removal list — the ordinal numbers of the remove requests whose results are displayed (for example, 1 4 means the costs removed by the first and the fourth remove requests are shown);
• the list of requests, each on its own line.

Each data set ends with an e request. Consecutive data sets are separated by empty lines.

For each remove request whose ordinal number is in the removal list, print the cost of the removed process; if the queue is empty at that moment, print -1 instead. Each printed value is on its own line, and an empty line separates the results of different data sets.