Double Queue

The newly founded Balkan Investment Group Bank (BIG-Bank) opened a new office in Bucharest, equipped with a modern computing environment provided by IBM Romania and using modern information technologies. As usual, each client of the bank is identified by a positive integer $K$ and, upon arriving at the bank for some service, receives a positive integer priority $P$. One of the inventions of the bank's young managers shocked the software engineer of the serving system: they proposed to break with tradition by sometimes calling to the serving desk the client with the lowest priority instead of the one with the highest priority. Thus, the system receives the following types of request:

• 0: The system needs to stop serving.
• 1 K P: Add client $K$ to the waiting list with priority $P$.
• 2: Serve the client with the highest priority and drop them from the waiting list.
• 3: Serve the client with the lowest priority and drop them from the waiting list.

Your task is to help the bank's software engineer by writing a program that implements the requested serving policy.

Each line of the input contains one of the possible requests; only the last line contains the stop request (code 0). You may assume that whenever there is a request to add a new client to the list (code 1), no client already in the list has the same identifier or the same priority. An identifier $K$ is always less than $10^6$, and a priority $P$ is always less than $10^7$. A client may arrive to be served several times, and may receive a different priority each time.

For each request with code 2 or 3, the program must print, on a separate line of the standard output, the identifier of the served client. If such a request arrives when the waiting list is empty, the program prints zero ($0$).