English version | [ver versão em português]

[PI051] - Clinic Chaos

Things are hectic at your local clinic.

With a surge in patients, managing the queue has become increasingly difficult. The clinic has asked for your help to restore order.

Task

Patients arrive at the clinic one by one, and from time to time, a patient is called in for consultation.

Each patient has one of three priority levels: A, B, or C. Priority A is the highest, followed by B, and then C.

When a patient is called in, the one with the highest priority who has been waiting the longest is chosen.

Your task is to determine the order in which patients are called.

Input

• The first line contains an integer n (1 ≤ n ≤ 50,000) — the number of events.
• Each event is described by either:
  • 1 — indicating a patient is called in (you should output the name of the patient selected), or
  • 0 — indicating a patient has arrived. In this case, two more lines follow:
    • A string with alphabetical characters (uppercase and/or lowercase) representing the patient's name.
    • A single character: A, B, or C, representing the patient’s priority level.

Output

For each event where a patient is called in (event 1), print the name of the selected patient.

Example Input 1

3
0
JoaquimExemplar
B
0
CarlosCoiso
A
1

Example Output 1

CarlosCoiso

Example Input 2

4
0
Jonas
C
0
Chabier
A
1
1

Example Output 2

Chabier
Jonas

Versão em Português | [see english version]

[PI051] - Caos na Clínica

Os tempos estão complicados na tua clínica local.

Com um aumento repentino no número de pacientes, gerir a fila de espera tornou-se uma tarefa difícil. A clínica pediu a tua ajuda para restaurar a ordem.

Objetivo

Os pacientes chegam à clínica um a um, e de tempos a tempos, um deles é chamado para consulta.

Cada paciente tem um dos três níveis de prioridade: A, B ou C. A prioridade A é a mais alta, seguida por B e depois C.

Sempre que alguém é chamado, é escolhido o paciente com maior prioridade que está à espera há mais tempo.

O teu objetivo é determinar a ordem em que os pacientes são chamados.

Input

• A primeira linha contém um número inteiro n (1 ≤ n ≤ 50.000) — o número de eventos.
• Cada evento é descrito por:
  • 1 — indicando que um paciente é chamado (deves imprimir o nome do paciente selecionado), ou
  • 0 — indicando que chegou um novo paciente. Neste caso, seguem-se mais duas linhas:
    • Uma string com letras (maiúsculas ou minúsculas) representando o nome do paciente.
    • Um único caractere: A, B ou C, indicando o nível de prioridade do paciente.

Output

Para cada evento em que um paciente é chamado (evento 1), imprime o nome do paciente selecionado.

Example Input 1

3
0
JoaquimExemplar
B
0
CarlosCoiso
A
1

Example Output 1

CarlosCoiso

Example Input 2

4
0
Jonas
C
0
Chabier
A
1
1

Example Output 2

Chabier
Jonas

Programação Imperativa (CC1003)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto