Problem B
Long Wait
Tom is selling some handmade items but demand for them has become very popular! Hundreds of people are queuing to order the items. Tom requests your help to write a program to keep track of people in the queue. Each person has a unique integer ID.
While people usually join the back of the queue, some are treated as VIPs and join the front of the queue. Tom also has a membership system in which a member can be slotted into the queue after the first $K$ people (or less, if the queue has less than $K$ people). Note that VIPs and members do not have their position fixed – Subsequent VIPs and/or members can push the positions of existing ones further back.
Your program needs to support the following operations which can be performed in any order:
-
queue x : person with ID x joins the back of the queue
-
member x : person with ID x joins the queue, now having ($K + 1$)th position (or less if there were $< K$ people in front)
-
vip x : person with ID x joins the queue, now having 1st position, pushing all other people in the queue back
-
slower : $K$ is increased by one, so members join the queue further back
-
faster : $K$ is decreased by one, so members wait less
-
findID pos : print the ID of the person at the position pos in the queue, on a new line
It is guaranteed that no one will join the queue more than once, that $K$ will never be less than 1 at all times, and that there will be a person at the position queried.
Input
The first line contains 2 integers $Q$ ($1 \le Q \le 800,000$) the number of operations to perform, and $K$ ($1 \le K \le 900,000$) the maximum number of people in front of a member who is about to join the queue.
Each of the next $Q$ lines contains one of the six operations described above. Each ID is a positive integer ($1 \le \textit{ID} < 10^{6}$)
Output
One line for each findID pos command. Each line contains a person ID.
| Sample Input 1 | Sample Output 1 |
|---|---|
20 2 member 11 queue 12 queue 13 findID 3 vip 91 vip 92 findID 1 member 41 member 42 findID 3 findID 5 faster member 43 findID 2 findID 3 slower slower member 44 findID 8 findID 4 |
13 92 42 11 43 91 12 44 |
