Kata

Many residents of Bitaculandia participate in the stages of international programming olympiads. There are seven such olympiads held in Bitaculandia:

1. IOI - International Olympiad in Informatics
2. CEOI - Central-Eventora Olympiad in Informatics
3. EGOI - Eventora Girls Olympiad in Informatics
4. EJOI - Eventora Junior Olympiad in Informatics
5. BaltOI - Balticodian Olympiad in Informatics
6. BalkOI - Balkolian Olympiad in Informatics
7. JBOI - Junior Balkolian Olympiad in Informatics

Miss M is responsible for organizing various stages of olympiads, as well as selections (training camps) for all seven international stages. After the last selection round, teams of four to six people are formed for all seven olympiads. However, only those participants who meet the criteria for participation in the olympiad should be sent to each competition. Here is a list of algorithms for determining the participants of the teams for the olympiads:

1. IOI - Top 4 participants based on the total scores from all selection rounds.
2. CEOI - Top 4 participants based on the total scores from all selection rounds.
3. EGOI - Top 4 female participants based on the total scores from all selection rounds.
4. EJOI - Top 4 participants at most 15 years old based on the total scores from all selection rounds.
5. BaltOI - Top 6 participants based on the total scores from all selection rounds.
6. BalkOI - Top 4 participants who are not in 11th grade based on the total scores from all selection rounds.
7. JBOI - Top 4 participants who are not in 11th or 10th grade based on the total scores from all selection rounds.

If there are fewer participants than the required number, it means that the team will consist of fewer people. For example, if you need to determine the team for EGOI and there are only two girls, it means that the team will consist of only two participants, not four. Since there are many participants and many olympiads, and the results are desired immediately after the competition ends, Miss M asks to write a program that, based on the results and information about the participants, provides the composition of the teams for the international stages of the olympiads.

Input:

First arguments contains list of n (1 ≤ n ≤ 10^4) string values, each contains information about the olympiad participants:

• id - unique participant number (10^6 ≤ id < 10^7);
• gender - participant’s gender (male, female);
• grade - participant’s grade level (1 ≤ grade ≤ 11);
• age - participant’s age (10 ≤ age ≤ 20);
• score - the number of points participants have from all selection rounds (0 ≤ score ≤ 10^8).

It is guaranteed that all ID and score of participants are different. Second arguments contains m (1 ≤ m ≤ 7) - list of international olympiads for which Miss M wants to know the composition of the participant teams. Possible olympiads: IOI, CEOI, EGOI, EJOI, BaltOI, BalkOI, JBOI. It is guaranteed that all olympiads are different.

Output:

Dictionary with m key-value pairs where key is name of olympiad (IOI, CEOI etc.) and value is list of participants IDs. Each list of IDs should be sorted by ascending. If no participants satisfy criteria of olympiad, add empty list for corresponding key.

Example:

participants = [
  '1000001 female 10 16 400',
  '1000002 male 10 17 500',
  '1000003 male 11 17 505',
  '1000004 male 11 16 405',
  '1000005 female 11 17 450',
  '1000006 female 10 15 480',
  '1000007 male 9 15 445',
  '1000008 male 6 12 350',
  '1000009 male 8 13 399',
  '1000010 male 10 16 430'
]
olympiads = [
  'IOI',
  'EGOI',
  'BaltOI'
]

advanced = who_advanced(participants, olympiads)
print(advanced)

{
  'IOI': [1000002, 1000003, 1000005, 1000006],
  'EGOI': [1000001, 1000005, 1000006],
  'BaltOI': [1000002, 1000003, 1000005, 1000006, 1000007, 1000010]
}

Explanation of example:

All participants can take part in IOI, the results table will look like this:

1. 1000003 - 505 points
2. 1000002 - 500 points
3. 1000006 - 480 points
4. 1000005 - 450 points
5. 1000007 - 445 points
6. 1000010 - 430 points
7. 1000004 - 405 points
8. 1000001 - 400 points
9. 1000009 - 399 points
10. 1000008 - 350 points

The participants who will go to the olympiad are 1000003, 1000002, 1000006, 1000005.

Only girls can participate in EGOI, the results table will look like this:

1. 1000006 - 480 points
2. 1000005 - 450 points
3. 1000001 - 400 points

The participants who will go to the olympiad are 1000006, 1000005, 1000001.

All participants can take part in BaltOI, the results table will look the same as for IOI. The same participants who will go to IOI will also go to BaltOI, as well as 1000007 and 1000010.

Adopted from Ukrainian Olympiad in Informatics 2023-2024, II stage