#1142 The One

1 s   128 MB  

Description

알고리즘 대회 개최에 중독된 LIBe는 2010년에도 어김없이 알고리즘 대회를 개최하였고, 이 대회의 우승자에게는 소정의 상금을 지급하기로 하였다.

 

대회에 상금이 걸린 만큼 참가자들의 호응이 좋았고, 직접 만든 대회 시스템이 별 문제없이 잘 돌아가자 LIBe는 가벼운 마음으로 여자친구와 놀러나갔다.

 

하지만, LIBe가 자리를 비운 사이 대회 시스템이 말썽을 일으켰다! 대회는 문제없이 종료되었지만, 여자친구와 놀다가 LIBe 는 시간 맞춰 돌아오지 못했고 대회 종료 루틴이 잘못 작성되어 DB 가 엉망이 되고 말았다. 이미 대회는 정상적으로 종료되어 참가자들은 모두 결과를 알고 있는 상황! 그러나 막상 주최자인 LIBe 는 DB 가 엉망이 되어 누가 우승자인지 판단할 수 없는 상황이 되었다.

 

다행스럽게도 DB 의 정보 중 일부가 복구되어 등록한 참가자들의 명단과 우승자의 등록번호를 얻을 수 있었고, LIBe 는 평소에 등록번호를 일정한 규칙에 따라서 발급하였기 때문에 우승자를 찾을 수 있게 되었다. 한번 크게 데인 LIBe 는 간단한 루틴이지만 직접 작성하는데 두려움을 느껴 여러분에게 우승자를 찾는 일을 부탁하게 되었다! LIBe 가 상금을 무사히 지급하고 패닉에서 벗어날 수 있도록 도와주자!

 

LIBe 가 참가자의 정보를 저장하는 방식은 다음과 같다.

 

1. 참가자의 정보는 이름과 성으로 구성되어 있다.

1) 참가자의 이름은 공백이 포함될 수 있으며 알파벳으로 이루어져있다.

2) 참가자의 성은 공백이 없는 알파벳으로 이루어져있다.

예를 들어 "Nana The Solo" 라는 이름이 주어졌을 경우 이름은 "Nana The"가 되고 성이 “Solo”가 된다.

2. 참가자들의 등록번호는 등록이 끝난 후, 한꺼번에 발급된다.

3. 참가자들의 정보는 정렬되어 저장된다.

1) 각 문자의 우선순위는 "AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz" 순으로 정렬된다.

2) 어떤 문자열이 다른 문자열의 Prefix(“abc", "abcde"와 같이 길이가 짧은 문자열이 긴 문자열의 앞부분과 일치하는 경우)일 경우 길이가 짧은 문자열의 우선순위가 낮다. 예를 들어 “abc", "abcde"가 있을 경우 “abc”가 “abcde"의 prefix이므로 "abc”가 "abcde"보다 낮은 우선순위를 가진다.

3) 성에 따라서 우선순위가 낮은 쪽에서 높은 쪽으로 정렬되며 성이 같을 경우 이름에 따라서 우선순위가 높은 쪽에서 낮은 쪽으로 정렬된다.

 

 

 

Input

 

첫 줄에는 테스트 케이스의 수 T 가 주어진다. T 는 20보다 작은 자연수이다.

각 테스트 케이스의 첫 줄에는 두 자연수 N(1 ≤ N ≤ 10000), K(1 ≤ K ≤ N) 가 주어진다.

N 은 참가자의 수, K 는 우승자의 등록번호이다.

다음 N 줄에는 각 참가자의 정보가 들어온다. 참가자의 정보는 이름과 성으로 이루어져 있으며 공백으로 구분된다. 참가자의 정보의 길이는 50을 넘지 않는다.

 

 

 

Output

 

우승자의 이름을 한 줄에 하나씩 출력한다.

 

 

Sample Input

Sample Output

1
5 4
LIBe The Dream
JongMan The Geek
Legend The Panic
Legend The Solo
Nana The Solo
Nana The Solo 

Source

2010 Ajou University Programming Contest