Common Words

Time limit1sMemory limit128 MB

Summary

For each data set, count word frequencies, find the k-th most common words, and print them alphabetically after a title line.

Level: Medium4 of 10
Topics: Hash map, Sorting, String, Implementation
Solved: No attempts yet

Problem

You are given a sequence of $m$ words taken from a newspaper article together with an integer $k$ . Find the $k$ -th most common word (or words).

Input

The first line contains an integer $n$ , the number of data sets. Each data set begins with a line holding two integers $m$ and $k$ , followed by $m$ lines. Each of those lines contains one word made of at most $20$ lowercase letters. A single data set contains at most $1\,000$ words.

Output

For each data set, determine the $k$ -th most common word(s). A word $w$ is the $k$ -th most common when exactly $k-1$ distinct words occur more frequently than $w$ . Such a word may not be unique (several words can tie for the $k$ -th place) or may not exist at all.

First print a title line <ordinal of k> most common word(s):, where the ordinal uses English notation (1st, 2nd, 3rd, 4th, 5th, …). Then print every word that is the $k$ -th most common, one per line, in ascending lexicographic (alphabetical) order. If no such word exists, print only the title line. Separate consecutive data sets with a single blank line.

Examples1

Example 1

Input

3
7 2
the
brown
the
fox
red
the
red
1 3
the
2 1
the
wash

Expected output

2nd most common word(s):
red

3rd most common word(s):

1st most common word(s):
the
wash