Problem Description

Given a sequence of $ N $ words $ S $ that make up a sentence, the same word may appear multiple times in this sequence. Output the $ K $-th word in the sequence when the words that appear at least once are sorted by their frequency of occurrence in descending order. If the $ K $-th word cannot be uniquely determined due to the same frequency of occurrence, output AMBIGUOUS instead.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ S_1 $ $ S_2 $ $ S_3 $ $\hspace{3pt}\ \vdots$ $ S_N $

Output Format

Output the $ K $-th word when the words that appear at least once in $ S $ are sorted by their frequency of occurrence in descending order. If the $ K $-th word cannot be uniquely determined, output AMBIGUOUS.

Sample Input and Output

Sample Input #1

6 2
abcde
caac
abcde
caac
abc
caac

Sample Output #1

abcde

Sample Input #2

9 3
a
a
bb
bb
a
ccc
bb
ccc
dddd

Sample Output #2

ccc

Sample Input #3

7 2
caac
abcde
caac
abc
abcde
caac
abc

Sample Output #3

AMBIGUOUS

Notes/Hints

Constraints

• $1 \le N \le 10^5$
• $ S_i $ is a string consisting of lowercase English letters with a length between $ 1 $ and $ 10 $ inclusive $(1 \le i \le N)$
• $1 \le K \le (\text{number of distinct strings in } S)$
• $ N $ and $ K $ are integers

Sample Explanation 1

caac appears $ 3 $ times, abcde appears $ 2 $ times, and abc appears $ 1 $ time. The $ 2 $-nd most frequent word is abcde.

Sample Explanation 2

a and bb appear $ 3 $ times each, ccc appears $ 2 $ times, and dddd appears $ 1 $ time. Regardless of the order of a and bb, they occupy the $ 1 $-st and $ 2 $-nd positions, making ccc the $ 3 $-rd most frequent word, so output ccc.

Sample Explanation 3

caac appears $ 3 $ times, and both abcde and abc appear $ 2 $ times each. The $ 2 $-nd most frequent word could be either abcde or abc, so output AMBIGUOUS.

见题面 Input 部分

见题面 Output 部分