Amrita University has been conducting ICPC regionals for several years. This year’s regionals is getting closer.
To select teams for onsite round, a preliminary online round is conducted. N teams have registered to participate in this year’s preliminary round, out of which M teams are to be selected for onsite round.
Rules for selection are as follows:
1. Maximum number of teams from a single institute can not exceed K.
2. The slots will be filled by selecting top ranking team from each institute according to the ranks in online round.
3. If slots are still available, the second ranking team from each institute will be selected. This procedure will continue to third ranking teams from each institute (subject to the above constraints) and so on, until vacancy exists. (See examples)
George has been given this important task of selecting M teams for onsite round. But he doesn’t know programming and he is too lazy to manually do the selection. So he has asked for your help. You are given the details of N teams which include:
Hi : Team name of ith team.
Ci : Institution name of the ith team.
The first line contains the number of test cases T.
Each test case starts with three integer N,M,K.
The next N lines contains two strings Hi and Ci.
Hi and Ci are strings which contains both lowercase and uppercase english alphabets and does not contain spaces.
Teams are ordered in ascending order of their ranking and no two team have the same team name for a given test case.
For each test case, if it is not possible to select M teams given the above rules, then print “Impossible”. Else print M lines containing the team names of the selected teams. Team name should be printed in ascending order of their ranking, ie top ranked team appear first.
After each test case leave an empty line.
Constraints1 ≤ T ≤ 10
1 ≤ M≤ N≤ 200000
1≤ K≤ 200
1≤ |Hi|,|Ci|≤ 20
Sum of N over all test cases≤200000
SubtasksSubtask #1 [40 points]: Sum of N over all test cases≤1000
Subtask #2 [60 points]: Original constraints
Input: 2 11 8 3 Spades IITR FacelessMen IITK Rocket IITB Randomly ANITS CodeTemp IITB Encore IITB Intuition Amrita Gap NIT Complexity Amrita MMM NIT Zap NIT 8 6 1 Triangulation IITR FruitSalad DAIICT Shockers IITM Survivor IITI limitless IIITH maniACs IITR Rainbow IIITH WhiteTigers IITR Output: Spades FacelessMen Rocket Randomly CodeTemp Intuition Gap Complexity
ExplanationFor first test case: Teams selected in first stage: Spades, FacelessMen,Rocket,Randomly,Intuition,Gap Teams selected in second stage: Since there are only 2 slots remaining therefore top 2 teams from different colleges will be selected. -> CodeTemp, Complexity
For second test case it is impossible to select 6 teams with at most 1 team per college.
All submissions for this problem are available.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions