ICPC to EC Final: Pig Team Advancement

A team in the Interactive Clever Pig Contest (ICPC) can advance to the Eating Contest Final (EC Final) under specific rules. There are \(m\) contests (numbered from 1 to \(m\)), and each contest has at most \(t\) teams participating. There are \(n\) ranking records. Each record contains the following information: team name, three distinct pig member names, contest number, and the team’s ranking in that contest.

We assume that pig names are globally unique: if two records share the same pig name then they refer to the same pig; however, every record is treated as a new team (even if the team name or pig names appear in an earlier record). The data guarantees that:

• Each team has exactly three distinct pig members.
• Within a contest, all team rankings are distinct.
• Within a contest, all pig members across teams are distinct.
• Within a contest, if a team with ranking \(r\) (\(r\ne 1\)) appears, then a team with ranking \(r-1\) must also appear.

The rule for advancing to EC Final is as follows:

A team is eligible to advance if and only if none of its pig members has advanced so far. Then, up to \(k\) operations are performed. In each operation, if there is no eligible team then the process stops. Otherwise, among all eligible teams, the team with the smallest ranking is chosen; if there is a tie in ranking then the team from the contest with the smallest contest number is selected. Once chosen, the team advances to the EC Final and all of its pig members are marked as advanced.

Your task is to output the names of the teams that advanced.

inputFormat

The first line contains four integers \(m\), \(t\), \(n\), and \(k\) (\(1 \le m, t, n, k \le 10^5\)). \(m\) is the number of contests, \(t\) is the upper bound of teams per contest, \(n\) is the number of ranking records, and \(k\) is the maximum number of advancement operations.

Each of the following \(n\) lines describes a team record with six tokens:

• team_name
• pig_member1
• pig_member2
• pig_member3
• contest_number (an integer)
• ranking (an integer)

Note that for each contest, the rankings are consecutive starting from 1, and no pig appears in more than one team in the same contest.

outputFormat

Output the names of the teams that advanced to the EC Final, one per line, in the order in which they advanced.

sample

2 2 3 2
TeamA pig1 pig2 pig3 1 1
TeamB pig4 pig5 pig6 1 2
TeamC pig1 pig7 pig8 2 1

TeamA
TeamB