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 |
| 1 | A | B | C |
| 2 | D | - | B |
| 3 | C | B | - |
| 4 | E | - | E |
| 5 | C | A | - |
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 1 in English |
| Problem B | Problem 3 in French |
| Problem C | Problem 5 in English |
| Problem D | Problem 2 in English |
| Problem E | 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).
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.
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.
4 5 3 ABC D-B CB- E-E CA- 3 2 AB C- -C 4 4 -A-- BB-- --CC --D- 3 4 AAAA BBBB CCCC
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
The judge input for this problem is randomly generated, so don't worry if your algorithm might fail on some deliberately hand-crafted test cases.