k번째로 자주 나오는 단어

신문 기사에서 뽑은 단어 $m$개가 순서대로 주어지고 정수 $k$가 주어질 때, $k$번째로 자주 나오는 단어(들)을 찾아라.

첫 줄에 데이터 집합의 개수 $n$이 주어진다. 각 데이터 집합은 두 정수 $m$과 $k$가 적힌 줄로 시작하고, 그 뒤에 $m$개의 줄이 이어진다. 각 줄에는 소문자 알파벳으로만 이루어진 길이 $20$ 이하의 단어가 하나씩 들어 있다. 한 데이터 집합에 들어 있는 단어는 $1,000$개를 넘지 않는다.

각 데이터 집합마다 $k$번째로 자주 나오는 단어(들)을 구한다. 어떤 단어 $w$가 $k$번째로 자주 나온다는 것은, $w$보다 더 자주 나오는 서로 다른 단어가 정확히 $k-1$개 있다는 뜻이다. 이런 단어는 여러 개일 수도 있고(공동 $k$위), 존재하지 않을 수도 있다.

먼저 제목 줄 <k의 서수> most common word(s):를 출력한다. 여기서 서수는 영어 표기(1st, 2nd, 3rd, 4th, 5th, …)를 따른다. 그 다음 $k$번째로 자주 나오는 모든 단어를 사전순(오름차순)으로 한 줄에 하나씩 출력한다. 해당하는 단어가 없으면 제목 줄만 출력한다. 서로 다른 데이터 집합 사이에는 빈 줄을 하나 넣어 구분한다.