Problem
Programming competitions are held annually in St. Petersburg, Barnaul and some cities of the near abroad. These competitions are held as part of the student world championship in programming, organized by one of the most respected associations ACM (Association for Computing Machinery). At these competitions, teams from the North-Eastern European Region NEERC (North-Eastern European Regional Contest) are selected. Every year, the organizers of the competition face the problem of determining the teams that will be invited to participate in the finals of the World Programming Championship. According to the new rules, no more than N teams representing NEERC go to the final. In addition, more than k teams cannot pass from one university. At the same time, from all such sets, the one in which the sum of places occupied by these teams in the semifinal competitions is the minimum possible is selected. Your task is to determine which teams will be invited to participate in the World Cup final based on the final protocol of the semi-final competitions and the numbers N and k.
Input
In the first line of the input file there are three natural numbers Р (1 ≤ P ≤ 100000) — the number of teams participating in the semi-final, N (1 ≤ N ≤ P ) and k (1 ≤ k ≤ P ) . The next P lines, one per line, list the names of the universities whose teams took the corresponding places. The name of the university contains lowercase and uppercase Latin letters and spaces. The length of the university name does not exceed 30 characters. The next line lists the team numbers of the respective universities. Thus, if the name of the university is written in the i -th line (2 ≤ i ≤ P + 1) , then this team took i - 1 place in the semi-finals and has a number written in i - 1 place in P + 2 line.
Output
In the output file print the names of the teams invited to participate in the finals of the World Programming Championship, sorted by the place occupied in the semi-finals. As the name of the team, print the name of the university followed by a space #the team number.
Example
| # |
Input |
Output |
| 1 |
9 5 2
Fantasy University
Crazy University
Fantasy University
Fantasy University
Very Good U
Good U
Very Good U
Crazy University
Good U
1 1 2 3 2 1 1 2 2
|
Fantasy University #1
Crazy University #1
Fantasy University #2
Very Good U #2
Good U #1
|