贝尔二十二世国王加冕即将来临!整个王室家族,包括贝尔二十二世的女儿们,都将出席。
国王已命令他的珠宝商组装 $$$n$$$ 漂亮的项链,因此每位公主在仪式上只能佩戴一条项链 - 现在这些项链已经完成。每条项链均由连接在金链上的 $$$m$$$ 宝石组成。项链中使用两种宝石——祖母绿和蓝宝石。因此,每条项链都可以由一系列 $$$m$$$ 宝石表示(从左到右列出),并且每颗宝石要么是祖母绿,要么是蓝宝石。形式上,第$$$i$$$条项链可以用长度为$$$m$$$的二进制字符串$$$s_i$$$表示;如果 $$$s_i$$$ 的第 $$$j$$$ 个字符为 0,则第 $$$i$$$ 项链中的第 $$$j$$$ 宝石为祖母绿;否则,这颗宝石就是蓝宝石。
现在,看着这些项链,国王担心他的一些女儿可能会羡慕其他女儿的项链。他希望所有项链看起来都相似。如果两条项链至少有 $$$k$$$ 个位置包含相同类型的宝石,则认为两条项链相似。
例如,如果有一条由序列 01010111 表示的项链和一条由序列 01100000 表示的项链,则这些项链有 $$$3$$$ 位置包含相同类型的宝石(第一颗宝石都是祖母绿,第二颗宝石都是蓝宝石,第五颗宝石都是祖母绿)。因此,如果 $$$k = 3$$$,则这些项链相似,如果 $$$k = 4$$$,则它们不相似。
国王认为,如果他的两个女儿注意到她们的项链不相似,那么她们可能会发生冲突——而且,显然,他不希望在加冕期间发生任何冲突!因此贝尔二十二世想告诉他的一些女儿将项链戴反。如果项链戴反了,那么这条项链中宝石的顺序就会颠倒。例如,如果一条项链由序列 01100 表示,那么如果反向佩戴,它将由序列 00110 表示。国王希望找到加冕期间反向佩戴的项链的最少数量,这样就不会发生冲突。
贝尔二十二世忙于准备加冕礼,所以他命令你帮他解决这个问题。帮助他——他会给你真正的皇家奖励!
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 50$$$) — 测试用例的数量。然后是测试用例。
每个测试用例都以包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ 的行开头 ($$$2 \le n \le 50$$$, $$$1 \le k \le m \le 50$$$) — 项链数量、每条项链中的宝石数量以及两条项链必须具有相同类型宝石的最小位置数为了分别看起来相似。
接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含一个长度为 $$$m$$$ 的二进制字符串 $$$s_i$$$,表示第 $$$i$$$ 条项链。
输出
对于每个测试用例,打印答案如下。
如果无法避免冲突,则在单行上打印-1。在这种情况下,您不应该为该测试用例输出任何其他内容。
否则,测试用例答案的第一行应包含单个整数 $$$d$$$ — 向后佩戴的项链的最小数量。测试用例答案的第二行应以任意顺序包含这些项链的编号(从 $$$1$$$ 到 $$$n$$$ 的整数)。如果 $$$d = 0$$$ 则将测试用例答案的第二行留空。如果有多个答案,您可以打印其中任何一个。
示例
输入 #1
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
输出 #1
2 1 3 1 3 0 -1 1 1