ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. The First Nonqualifying

Time limit: 0.5 second
Memory limit: 64 MB
Any participant of an ACM ICPC Regional contest knows that it is very annoying to take the place that is the first nonqualifying for the World Finals. It often happens that a team falls very short of getting into the Finals.
For example, in 1999 a team of the Ural State University took the tenth place at the Northeastern European Regional Contest, and only 6 minutes of penalty time kept it from getting into the Finals. The last qualifying ninth place was then taken by a team of the St. Petersburg Institute of Fine Mechanics and Optics. In 2006 the distance between the last qualifying and the first nonqualifying places was as small as 4 minutes of penalty time. However, between teams of the Kazakh National University and the St. Petersburg Polytechnical University there was the third team of the Saratov State University, which could not go to the Finals because the second team of the same university had 2 more solved problems.
The Northeastern European Region, which holds Regional contests in which all Russian teams take part, is given every year some quota q for representing this region in the World Finals. According to the ACM ICPC rules, no two teams of the same university may take part in the Finals. That is why, when it is decided who goes to the Finals, any team that has worse results than some other team of the same university is excluded from the protocol. The (q + 1)th place in the resulting list is called the first nonqualifying. If the regional quota were increased by one place, then the team that took that place would get into the Finals.


The first line contains the year y when a Northeastern European Regional Contest was held (an integer from 1996 to 2008), the number of participating teams n ≤ 201, and the quota q for the World Finals (an integer from 3 to 12). The numbers are separated with a space. In the following n lines you are given the resulting protocol in the form of a list of the names of teams in the order of places they took at the contest. The name of each team consists of the name of its university and the number of the team separated from the name of the university by a space and symbol '#'. If a university was presented by only one team, then its name may consists of the name of the university only. The names of universities consist of English letters, spaces, symbols '.', '-', and '&'; they are no longer than 36 symbols. The names of two universities can't differ by the case of the letters only. The number of a team is an integer from 1 to 8.


Output the name of the team that took the first nonqualifying place at this semi-final. It is guaranteed that such a team exists.


1999 10 6
St Petersburg SU #1
Belarusian SU #1
Moscow SU #4
Southern Ural SU
Moscow SU #1
Novosibirsk SU #1
St Petersburg SU #3
Belarusian SU #3
St Petersburg IFMO #1
Ural SU #3
Ural SU #3
Problem Author: Dmitry Ivankov (prepared by Alexander Ipatov)
Problem Source: USU Open Personal Contest 2009 (February 28, 2009)
To submit the solution for this problem go to the Problem set: 1680. The First Nonqualifying