collections.deque

Lab Python Intermediate 20 points

Simulate a queue at a ticket counter. Commands: join NAME, serve (print the served name or nobody), vip NAME (joins at the front). At the end print the remaining queue or empty.

Input

Line 1: n. Then n commands.

Output

Served names, then the queue.

Example

Input

6
join ann
join bob
vip zed
serve
serve
join cy

Output

zed
ann
bob cy

Sample input available Sample output available

Editor

Python

Hints

deque supports fast append/pop at both ends.

list.pop(0) is slow for big queues; deque.popleft() is fast.

Solution explanation

Use deque whenever you add or remove items at the front.

Show solution

from collections import deque

queue = deque()
for _ in range(int(input())):
    cmd, *rest = input().split()
    if cmd == "join":
        queue.append(rest[0])
    elif cmd == "vip":
        queue.appendleft(rest[0])
    else:
        print(queue.popleft() if queue else "nobody")
print(*queue if queue else ["empty"])

Output

Answer