题目描述

Vincent and Desta are childhood friends. Today, Vincent is showing $N$ distinct $L$-letter words to Desta by using some letter tiles. Each tile contains one uppercase English alphabet letter, and one number between $1$ and $L$. A word consists of the letters spelled out by $L$ tiles with numbers from $1$ through $L$, in order. (Vincent's words are not necessarily real English words.)

For example, if Vincent has $N = 3$ words with $L = 4$, and the words are $\{\text{CAKE}, \text{TORN}, \text{SHOW}\}$, then Vincent must show the following to Desta:

Desta feels that creating words must be easy, and he wants to create a new word that obeys the rules above and is not one of Vincent's existing words. However, Desta does not have any tiles of his own, so he must use some of Vincent's tiles.

For instance, if Vincent has the words from the previous example, then Desta can make a new word such as $\text{CORN}$ or $\text{SAKE}$ or $\text{CHRE}$ (Desta's words are also not necessarily real English words). Each of the example is illustrated in the following image:

Note that the three rows in the image above are independent. Desta only needs to make one new word.

However, in the above example, Desta cannot make WAKE, for example, because there is no $\text W$ tile with a number $1$. Nor can he make coo, since it is not the right length.

Notice that it may be impossible for Desta to make a new word. For example, if Vincent has only one word, then Desta cannot make anything new. Or, if Vincent has the words $\{\text{AA}, \text{AB}, \text{BA}, \text{BB}\}$, then any word that Desta can form is already present.

Help Desta to choose a word that he can show to Vincent using only the tiles used by Vincent, or indicate that it is impossible to do so.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each begins with one line with two integers $N$ and $L$: the number of Vincent's words, and the length of each word. Then, $N$ more lines follow. The $i$-th of these lines contains a string of $L$ uppercase English letters representing the $i$-th of Vincent's words.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is a valid word to be chosen by Desta, or - (a single dash character of ASCII value 45) if there is no valid word to be chosen by Desta. If there is more than one valid word that Desta can make, you can output any of them.

5
4 1
A
B
C
D
4 2
WW
AA
SS
DD
4 2
AA
AB
BA
BB
3 4
CAKE
TORN
SHOW
5 7
HELPIAM
TRAPPED
INSIDEA
CODEJAM
FACTORY

Case #1: -
Case #2: WA
Case #3: -
Case #4: CORN
Case #5: HOLIDAY

提示

Sample Explanation

Note that the last two sample cases would not appear in test set 1.

In Sample Case #1, the only words that can be constructed using the tiles used by Vincent are A, B, C, D. However, all of those words already appear in Vincent's list of words, so Desta is not allowed to choose them.

In Sample Case #2, there are $12$ possible new words that Desta can make, one of which is $\text{WA}$.

Sample Case #3 was explained in the problem description above; there is no new word that Desta can make.

Sample Case #4 was explained in the problem description above; other answers such as $\text{SAKF}$ are possible.

In Sample Case #5, other answers such as $\text{TRAPJAM}$ are possible.

Limits

• $1 \leqslant T \leqslant 100$.
• No two of Vincent's words are the same.

Test set 1 (11 Pts, Visible)

• $1 \leqslant N \leqslant 26^{2}$.
• $1 \leqslant L \leqslant 2$.

Test set 2 (17 Pts, Hidden)

• $1 \leqslant N \leqslant 2000$.
• $1 \leqslant L \leqslant 10$.