Challenge: Emergency Room

Lab C++ Intermediate 20 points

Process n events: arrive <name> <priority> (1 = most urgent) and treat, which prints the name of the most urgent patient (earliest arrival on a tie), or 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

C++

Hints

Use a min-heap of (priority, arrival number, name).

The arrival number breaks ties in arrival order.

Solution explanation

Tuples compare item by item, so the arrival number only matters when priorities tie.

Show solution

#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<tuple<int, int, string>, vector<tuple<int, int, string>>, greater<tuple<int, int, string>>> pq;
    int order = 0;
    while (n--) {
        string cmd;
        cin >> cmd;
        if (cmd == "arrive") {
            string name;
            int pr;
            cin >> name >> pr;
            pq.push({pr, order++, name});
        } else if (pq.empty()) {
            cout << "nobody" << endl;
        } else {
            cout << get<2>(pq.top()) << endl;
            pq.pop();
        }
    }
    return 0;
}

Output

Answer