Challenge: Emergency Room

Lab Python Intermediate 20 points

Process n events. arrive <name> <priority> adds a patient (priority 1 is the most urgent). treat treats the most urgent patient and prints their name; if two have the same priority, the one who arrived first is treated first. If nobody is waiting, print nobody.

Input

Line 1: n. Then n events.

Output

One line per treat.

Example

Input

6
arrive Asha 3
arrive Ravi 1
arrive Meera 1
treat
treat
treat

Output

Ravi
Meera
Asha

Sample input available Sample output available

Editor

Python

Hints

Push (priority, arrival_number, name).

The arrival number breaks ties so earlier patients go first.

Solution explanation

A tuple's later items only matter when earlier ones tie – perfect for “then by arrival order”.

Show solution

import heapq
n = int(input())
heap = []
order = 0
for _ in range(n):
    parts = input().split()
    if parts[0] == "arrive":
        heapq.heappush(heap, (int(parts[2]), order, parts[1]))
        order += 1
    elif heap:
        print(heapq.heappop(heap)[2])
    else:
        print("nobody")

Output

Answer