406708: GYM102503 E Who Gets Medals

Your friend did not read the rules for qualifying to the NOI.PH on-site finals round. He wants to know who gets invited and who are eligible for medals. Luckily, you read the rules written at the official NOI.PH rules page, https://noi.ph/rules, and are able to explain to your friend how it works. In fact, you decide to make a program that automates this for your friend.

There are several numbers on the rules which we will vary for this problem. They are the following:

• The initial value $$$c$$$ of Cap.
• the maximum number $$$s$$$ of finalists allowed per school. For the $$$2020$$$ edition of the contest, $$$s = 6$$$ according to III.3.1.4. Every occurrence of $$$6$$$ in the rules is replaced by $$$s$$$.
• the maximum number $$$f$$$ of finalists allowed. For the $$$2020$$$ edition of the contest, $$$f = 30$$$ according to III.3.1. Every occurrence of $$$30$$$ in the rules is replaced by $$$f$$$.
• the shortlist will be the union of the following sets of participants:
  • the top $$$p$$$ participants, based on the official scoreboard. For the $$$2020$$$ edition of the contest, $$$p = 40$$$ according to the first bullet point of VII.3.1.
  • the top $$$q$$$ school-qualifying participants. For the $$$2020$$$ edition of the contest, $$$q = 40$$$ according to the second bullet point of VII.3.1.

For this problem, you will be given the data of the official scoreboard, containing only eligible participants and not containing disqualified participants. In particular, you will be given the username, the first name, the last name, the school, the score, and the time penalty of a contestant in the Elimination Round. Assume that no two people with the same score have the same time penalty. The data is not necessarily given in any particular order.

We will simulate the chain of events after the elimination round but before the finals. We will detail it here, in words. You may refer to the input format for more specific details on how these events will be communicated. We will not include observers in this simulation; assume that there will be no observers.

A participant is said to be invited (to attend the on-site finals) if and only if the participant is in the shortlist. Exactly one invitation will be sent to each invited participant and contains a confirmation of whether the participant is willing and able to attend the on-site finals or not. An invited participant may either accept or decline.

Participants in the waitlist are still invited, although they are only confirming their willingness and ability to attend the on-site finals in case they get promoted to either an official finalist or a non-finalist participant.

With respect to individual participants, the following events may happen:

• a participant becomes disqualified.
• an invited participant accepts the invitation.
• an invited participant declines the invitation.

With respect to logistics, the following can happen:

• the deadline for confirmation passes. This only happens once.
• Cap changes its value.

At any time during these events, we can query the contents of the following lists, sorted by rank (as described in the rules page).

• the (ordered) list of official finalists.
• the (ordered) list of non-finalist participants.
• the (ordered) list of waitlisted participants.

Some events may be invalid. Here is the list of criteria for when an event is valid or invalid.

• Each participant can only accept once and can only decline once. If a participant accepts a second time or declines a second time, then such an event is invalid. For the purposes of this criterion, a disqualification is equivalent to a declination.
• A participant may decline even if he/she has accepted earlier.
• An event where a non-invited participant accepts or declines an invitation is considered invalid. For the purposes of this criterion, a disqualification is NOT considered a declination.
• Any student in the official scoreboard can be disqualified. In particular, students who are in the official scoreboard but not in the initial shortlist may be disqualified. Such an event is considered valid if and only if the student has not been disqualified before. When a student not in the initial shortlist is disqualified, nothing happens to the shortlist.
• Any event which contradicts the NOI.PH rules (with the updated numbers) is invalid.
• Any other event is considered valid.

The first line of input contains a single integer $$$t$$$ denoting the number of test cases.

The first line of each test case contains five space-separated integers $$$c$$$, $$$s$$$, $$$f$$$, $$$p$$$, $$$q$$$ in that order, the values they represent are written in the problem statement.

The next several lines contain data about the official scoreboard. Each of those lines will be of the following form:

USERNAME/FIRSTNAME/LASTNAME/SCHOOL/SCORE/PENALTY

USERNAME, FIRSTNAME, LASTNAME, SCHOOL, SCORE and PENALTY is the username, first name, last name, school, score and time penalty of the student being described.

If the line is not of the above form, then the line is guaranteed to be END OF SCOREBOARD. This line marks the end of the input concerning the data of the official scoreboard.

The next several lines of input are either events or queries. The events are of the following form:

• DQ $$$u$$$, which means that the participant with username $$$u$$$ has been disqualified.
• AC $$$u$$$, which means that the participant with username $$$u$$$ has accepted the invitation.
• DE $$$u$$$, which means that the participant with username $$$u$$$ has declined the invitation.
• CAP $$$c'$$$, which means that the value of Cap is updated to $$$c'$$$.
• CONFIRMATION DEADLINE, which means that the deadline for confirmation has passed. This event will happen exactly once for each test case.
• PRINT NAMETAGS, which means that the input for this test case is done, and no more events or queries follow. Clearly, this string will appear exactly once for each test case.

Comparing any two strings should be done case insensitively (i.e., Kevin and keVIN are viewed to be the same string).

The queries are of the following form:

• OF $$$i$$$, which means that your program must output the username of the $$$i$$$th participant in the current ordered list of official finalists.
• NP $$$i$$$, which means that your program must output the username of the $$$i$$$th participant in the current ordered list of non-finalist participants.
• WL $$$i$$$, which means that your program must output the username of the $$$i$$$th participant in the current ordered list of waitlisted participants.

For each event, if it is valid, process it and output a single line containing the integer $$$1$$$; if it is not valid, output a single line containing the integer $$$0$$$.

For each query, output the username of the participant who is currently in the $$$i$$$th position of the specified list. (We mention "currently" to clarify that valid events happening before the query may change the contents of the list.) If the specified list contains less than $$$i$$$ participants, print the string DOES NOT EXIST instead.

When outputting a username, it should exactly match how it is given in the input, including case.

After processing the last event (PRINT NAMETAGS), output a sorted list of all participants who are coming to the finals. Output each entry of the list, in order, using the following format:

LASTNAME, FIRSTNAME/SCHOOL/STATUS/MEDALS?

(Note that there is a space after the comma.)

Here, FIRSTNAME and LASTNAME are the first and last names of the student. SCHOOL is their school. STATUS is one of the following:

• OF if the student is an official finalist.
• NP if the student is a non-finalist participant.

MEDALS? must be YES if the attendee is eligible to receive medals. Otherwise, it must be NO.

This list, unlike the queries (which are sorted by rank), must be alphabetically sorted by last name. Ties for the last name are broken by first name. Ties for the first name are broken by username. The username is unique and therefore there should be no ties at all. Any two strings must be compared lexicographically. Comparing two strings should be done case insensitively (i.e., Kelvin and kelVIN are viewed to be the same string). The lexicographic ordering of all valid characters is: [space]_abcdefghijklmnopqrstuvwxyz0123456789, where [space] represents the space character.

We denote the number of entries in the official scoreboard by $$$n$$$, and the number of events and queries $$$e$$$.

$$$1 \le t \le 10^4$$$

$$$1 \le n \le 10^5$$$

$$$2 \le e \le 10^5$$$

The sum of the $$$n$$$s in a single test file is $$$\le 10^5$$$

The sum of the $$$e$$$s in a single test file is $$$\le 10^5$$$

$$$1 \le c', c, s, f, p, q \le 10^5$$$

$$$c', c \ge f$$$

USERNAME and $$$u$$$ are nonempty strings of at most $$$24$$$ characters that can only contain letters, underscores and numbers.

FIRSTNAME, LASTNAME, SCHOOL are nonempty strings that can only contain letters and spaces.

SCORE and PENALTY are positive integers with value at most $$$10^9$$$.

The USERNAME, FIRSTNAME, LASTNAME and SCHOOL is at most $$$100$$$ characters in total.

The USERNAMEs that appear on the official scoreboard are unique.

For each query, $$$1 \le i \le 10^5$$$

Each FIRSTNAME, LASTNAME and SCHOOL does not contain leading or trailing spaces and does not contain two consecutive spaces.

No two participants with the same score have the same time penalty.

Subtask 1 (20 points):

$$$n \le 1000$$$

$$$e \le 1000$$$

The sum of the $$$n$$$s in a single file is not over $$$9000$$$

The sum of the $$$e$$$s in a single file is not over $$$9000$$$

$$$c', c \le 100$$$

$$$s = 6$$$

$$$f = 30$$$

$$$p = q = 40$$$

Subtask 2 (38 points):

$$$n \le 1000$$$

$$$e \le 1000$$$

The sum of the $$$n$$$s in a single file is not over $$$9000$$$

The sum of the $$$e$$$s in a single file is not over $$$9000$$$

$$$c', c, s, f, p, q \le 100$$$

Subtask 3 (27 points):

Cap never decreases.

Subtask 4 (15 points):

No additional constraints.

1
30 5 12 25 29
bimb/Bimby/Aquino/Pilipinas School KNB/1000/3
spacestalker/Space/Stalker/Our Lady of Perpetual Sorrow High School Other Campus/999/1
chakalakachakalaka/Chakalaka Chakalaka/Boom/Our Lady of Perpetual Sorrow High School Main Campus/999/2
boypickup/Pickup/Boy/Jejeman Senior High/10/3
packing69/Miguel/Enriquez/Our Lady of Perpetual Sorrow High School Other Campus/999/4
bbgurl/Pabebe/Gurl/Our Lady of Perpetual Sorrow High School Main Campus/999/5
suptokao/Supokato/Dipakotliu/Our Lady of Eternal Bleeding High School/10/6
g00db0y/Good/Boy/Jejeman Senior High/10/7
denzel/Denzel/Wetta/Disc III Junior High/10/8
troll5/Zzzzyzyzzyzz/Aaaabbaab/Our Lady of Perpetual Sorrow High School Other Campus/999/51
troll9/Zzzzyzyzzyz/Aaaabbaab/Our Lady of Perpetual Sorrow High School Other Campus/999/9
keribells/Bells/Keri/Our Lady of Perpetual Sorrow High School Other Campus/999/11
keriboomboom/Boomboom/Keri/Our Lady of Perpetual Sorrow High School Other Campus/999/12
xXx_alliwant4xXxmas_xXx/Mariah/Keri/Our Lady of Perpetual Sorrow High School Main Campus/999/13
bogart/Bogart/Bogart/Our Lady of Questionable Choices High School/10/14
vanilla/Vanilla/Ice Ice Baby/Mount Mayon Elementary School/2/4
spwet/Spwet/Spwetot/Mount Mayon Elementary School/15/5
pepe/Pe/Pe/Pe/789/495
pepepe/Pe/Pepe/Pe/798/801
pe_pepe/Pe/Pe Pe/Pe/782/512
pepe_pe/Pe Pe/Pe/Pe/798/43
jason/Jason/ILoveGames/MaTURONgin Erementaly Schoor/9/550
plutarcoplutarco/Plutarco/Plutarco/Plutarco/7/818
empoy/Empoy/Brandy/Our Lady of Generous Giving High School/6/967
barce/Barce/Brandy/Our Lady of Generous Giving High School/16/59
grammy/Gramatdor/Tandy/Our Lady of Generous Giving High School/15/4
easilyamazed/Wow May Comma Before This Sentence/Wow May Comma After This Sentence/Scool Bcool/1/9
ginny/Ginebrador/Tandy/Our Lady of Generous Giving High School/3/2
realhuman/Juan/de la Cruz/Totally Human School/18/1
cassandra/Cassandra/de la Cruz/Our Lady of Perpetual Sorrow High School Other Campus/2/9
kuyakim/Kim/Atienza/Our Lady of Otaku Elementary School/9/9
chuuyachim/Nakahara/Chuuya/Our Lady of Otaku Elementary School/2/537
nittanurtter/Hina/Nitta/Our Lady of Otaku Elementary School/13/3
emma1andonly/Emma/Doqueza de Jesus Fuentabella/Barangay Adamya Elementary School/5/167
genevaconvention/Geneva/Ferrer Takahashi/Barangay Adamya Elementary School/9/773
nadinepadine/Nadine/Lustre/Barangay Adamya Elementary School/8/901
yourbestreid/James/Reid/Barangay Adamya Elementary School/19/3
jedith/Kylo/Rey/Death Star University/5/5
jingding/JD/Dantes/Ateneo de Diliman University of the Philippines Manila Campus/11/11
max_cost_min_flow/Kyle/See/University of Ford Fulkerson/55/55
fetch/Payton/Yao/South Shore High School/80/80
cgpgray01/Catriona/Gray/Our Lady School/8/677
cgpgray02/Catriona/Gray/Our Lady School/18/2
cgpgray03/Catriona/Gray/Our Lady School/4/453
cgpgray04/Catriona/Gray/Our Lady School/11/1
cgpgray05/Catriona/Gray/Our Lady School/17/3
cgpgray06/Catriona/Gray/Our Lady School/18/5
cgpgray07/Catriona/Gray/Our Lady School/20/3
cgpgray08/Catriona/Gray/Our Lady School/14/8
cgpgray09/Catriona/Gray/Our Lady School/3/923
cgpgray10/Catriona/Gray/Our Lady School/10/947
cgpgray11/Catriona/Gray/Our Lady School/316/23
cgpgray12/Catriona/Gray/Our Lady School/7/722
cgpgray13/Catriona/Gray/Our Lady School/19/2
cgpgray14/Catriona/Gray/Our Lady School/17/131
cgpgray15/Catriona/Gray/Our Lady School/19/7
cgpgray16/Catriona/Gray/Our Lady School/19/206
cgpgray17/Catriona/Gray/Our Lady School/18/6
cgpgray18/Catriona/Gray/Our Lady School/9/1
cgpgray19/Catriona/Gray/Our Lady School/6/213
cgpgray20/Catriona/Gray/Our Lady School/10/984
cgpgray21/Catriona/Gray/Our Lady School/6/7
cgpgray22/Catriona/Gray/Our Lady School/18/3
cgpgray23/Catriona/Gray/Our Lady School/14/945
cgpgray24/Catriona/Gray/Our Lady School/317/5
and_so_on/Catriona/Gray/Our Lady School/16/10
cgpgray49/Catriona/Gray/Our Lady School/13/8
cgpgray50/Catriona/Gray/Our Lady School/14/10
END OF SCOREBOARD
DQ bogart
AC supokato
AC pepe
AC spacestalker
AC chakalakachakalaka
OF 50
AC packing69
AC bbgurl
AC keribells
AC keriboomboom
AC xXx_alliwant4xXxmas_xXx
AC boypickup
DQ boypickup
DQ g00db0y
DE denzel
OF 1
AC sutpokao
DE troll9
AC barce
AC grammy
AC cgpgray02
AC cgpgray11
AC cgpgray24
AC cgpgray9999
AC NittaNurtter
AC pe_PEPE
AC troll5
AC troll9
DE troll9
DQ realhuman
NP 2
AC pepe_pe
AC troll9
DE troll5
AC troll9
DE troll9
AC troll9
DE troll5
AC troll5
AC pepepe
OF 3
CONFIRMATION DEADLINE
OF 3
DE troll9
AC troll9
AC bimb
WL 2
DE troll5
AC troll9
DE troll9
AC troll9
DE troll5
OF 3
PRINT NAMETAGS

1
0
1
1
1
DOES NOT EXIST
1
1
1
1
1
1
1
1
0
bimb
0
1
1
1
1
1
1
0
1
1
1
0
0
1
cgpgray24
1
0
1
0
0
0
0
0
1
chakalakachakalaka
1
packing69
0
0
0
DOES NOT EXIST
0
0
0
0
0
packing69
1
Boom, Chakalaka Chakalaka/Our Lady of Perpetual Sorrow High School Main Campus/OF/YES
Brandy, Barce/Our Lady of Generous Giving High School/NP/NO
Enriquez, Miguel/Our Lady of Perpetual Sorrow High School Other Campus/OF/YES
Gray, Catriona/Our Lady School/NP/NO
Gray, Catriona/Our Lady School/NP/NO
Gray, Catriona/Our Lady School/OF/YES
Gurl, Pabebe/Our Lady of Perpetual Sorrow High School Main Campus/OF/YES
Keri, Bells/Our Lady of Perpetual Sorrow High School Other Campus/OF/YES
Keri, Boomboom/Our Lady of Perpetual Sorrow High School Other Campus/OF/YES
Keri, Mariah/Our Lady of Perpetual Sorrow High School Main Campus/OF/YES
Nitta, Hina/Our Lady of Otaku Elementary School/NP/NO
Pe, Pe/Pe/OF/YES
Pe, Pe Pe/Pe/OF/YES
Pe Pe, Pe/Pe/OF/YES
Pepe, Pe/Pe/OF/YES
Stalker, Space/Our Lady of Perpetual Sorrow High School Other Campus/OF/YES
Tandy, Gramatdor/Our Lady of Generous Giving High School/NP/NO