Double Queue#790
Recently, the Balkan Investment Bank Group (BIG-Bank) opened a new office in Bucharest, equipped with a modern computing environment provided by IBM Romania and using modern information technologies. Each client of the bank is identified by a natural number . When a client comes to the bank for services, they are assigned a certain natural number — a priority . The young managers of the bank proposed to serve either the client with the highest priority or the one with the lowest priority first, breaking the tradition.
The system receives the following types of requests:
— Stop the client service system
— Add client with priority to the waiting list
— Serve the client with the highest priority and remove them from the waiting list
— Serve the client with the lowest priority and remove them from the waiting list
You need to help the bank's software engineer by writing a program that implements this servicing rule.
Each input line contains one of these possible requests; only the last line contains the stop request (code ). When a request to add a client to the list (code ) is given, assume there are no other requests involving this client or a client with the same priority at that time. The value of is always less than 10^6, and the priority is less than 10^7. A client may come and receive services several times, each time receiving a different priority.
For each request with code or , output on a separate line the identifier of the served client. If a request arrives when the waiting list is empty, output zero ().
Example 1