If you speak German, you should know the first word in the title. If you speak Italian, you should know the second one :) Why I use these two words? Because I don’t have better choices :( I want my problems’ titles to start with A, B, C, etc. This is problem Q so it has to begin with the letter Q. Sometimes it’s difficult. Each problem title has to tell people something about the problem itself, so it can’t be arbitrary. If I can’t find a suitable title in English, I have to try other languages like Chinese (for example, see the last three problems in Rujia Liu’s Present 5 ^_^). Here is an example. No English French Chinese 1ABC 2D-B 3CB- 4E-E 5CA- The title of problem 1 in English starts with A, and the French version starts with B. The Chinese title of problem 1 starts with C. A hyphen means “N/A”, so problem 2 doesn’t have a French version. One possible combination is (note that each problem should be used exactly once): Problem A Problem B Problem C Problem D Problem E Problem 1 in English Problem 3 in French Problem 5 in English Problem 2 in English Problem 4 in Chinese Could you tell me all the possible language combinations? For each combination, all the languages in it must be used (i.e. You can’t say the combination is English,Chinese if none of the problems actually used the Chinese version). Input The first line contains the number of test cases T (T ≤ 500). Each test case begins with two integers n, m (3 ≤ n ≤ 26, 1 ≤ m ≤ 5), the number of problems and the number of languages. The next n lines contains the table containing the first m upper-case letters or ‘-’. The j-th column in the i-th row in the table is the first letter of the title in the j-th language. A special character ‘-’ means that version does not exist. Output For each test case, print all possible combinations in a single line. Each combination is a string of languages used (languages are labeled 1 to m) in increasing order. Shorter combinations should come first. Combinations of the same length should be sorted in increasing order. If the problemset cannot be made, print ‘-1’.
2/2 Sample Input 4 53 ABC D-B CB- E-E CA- 32 AB C- -C 44 -A-- BB-- --CC --D- 34 AAAA BBBB CCCC Sample Output Case 1: 12 123 Case 2: -1 Case 3: 23 123 234 1234 Case 4: 1 2 3 4 12 13 14 23 24 34 123 124 134 234