A13035 | The Coronation

The coronation of King Berl XXII is soon! The whole royal family, including $n$ daughters of Berl XXII, will be present.

The King has ordered his jeweler to assemble $n$ beautiful necklaces, so each of the princesses could wear exactly one necklace during the ceremony — and now these necklaces are finished. Each necklace consists of $m$ gems attached to a gold chain. There are two types of gems used in the necklaces — emeralds and sapphires. So, each necklace can be represented by a sequence of $m$ gems (listed from left to right), and each gem is either an emerald or a sapphire. Formally, the $i$ -th necklace can be represented by a binary string $s_i$ of length $m$ ; if the $j$ -th character of $s_i$ is 0, then the $j$ -th gem in the $i$ -th necklace is an emerald; otherwise, this gem is a sapphire.

Now, looking at the necklaces, the King is afraid that some of his daughters may envy the other daughters' necklaces. He wants all necklaces to look similar. Two necklaces are considered similar if there are at least $k$ positions where these necklaces contain the same type of gems.

For example, if there is a necklace represented by a sequence 01010111 and a necklace represented by a sequence 01100000, then there are $3$ positions where these necklaces contain the same type of gems (both first gems are emeralds, both second gems are sapphires, and both fifth gems are emeralds). So if $k = 3$ , these necklaces are similar, and if $k = 4$ , they are not similar.

The King thinks that if two of his daughters notice that their necklaces are not similar, then they may have a conflict — and, obviously, he doesn't want any conflicts during the coronation! So Berl XXII wants to tell some of his daughters to wear their necklaces backward. If a necklace is worn backward, then the sequence of gems in this necklace is reversed. For example, if a necklace is represented by a sequence 01100, then, if worn backward, it would be represented by a sequence 00110. The King wants to find the minimum number of necklaces to be worn backward during the coronation so that there are no conflicts.

Berl XXII is too busy with preparation for the coronation, so he ordered you to resolve this issue for him. Help him — and he will give you a truly royal reward!

The first line contains one integer $t$ ( $1 \le t \le 50$ ) — the number of test cases. Then the test cases follow.

Each test case begins with a line containing three integers $n$ , $m$ and $k$ ( $2 \le n \le 50$ , $1 \le k \le m \le 50$ ) — the number of necklaces, the number of gems in each necklace, and the minimum number of positions where two necklaces have to have the same type of gems in order to look similar, respectively.

Then $n$ lines follow, the $i$ -th of them contains a binary string $s_i$ of length $m$ representing the $i$ -th necklace.

For each test case, print the answer as follows.

If it is impossible to avoid the conflict, print -1 on a single line. In this case you should not output anything else for that test case.

Otherwise, the first line of the test case answer should contain the single integer $d$ — the minimum number of necklaces that are to be worn backward. The second line of the test case answer should contain the numbers of these necklaces (integers from $1$ to $n$ ) in any order. If $d = 0$ then leave the second line of the test case answer empty. If there are multiple answers, you may print any of them.