Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. The Coronation

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThe 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!

Input

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.

Output

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.

Example

Input

5 5 7 2 1010100 0010101 1111010 1000010 0000101 6 9 3 011111110 100111000 111100000 000111111 110100111 111110111 3 4 2 0001 1000 0000 3 4 4 0001 1000 0000 2 4 3 0001 1000

Output

2 1 3 1 3 0 -1 1 1

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/23/2020 09:06:10 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|