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.

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.