PARITY  Parity
You are given n binary strings s_{1},...,s_{n}, each of the same length m. Along with each s_{i} you are given a bit b_{i}. You are also given some nonnegative integer k and want to know whether there exists a subset S of {0,1,...,m1} of size at most k such that for each i=1,2,...,n, the bit b_{i} is the XOR of the bits of s_{i} at the indices in S. The s_{i} are 0indexed strings. Recall that the XOR of a set of bits is 1 if the number of bits equal to 1 is odd, else the XOR is 0 (in particular, the XOR of an empty set of bits is 0). For example, if s_{1} = 1010 and S = {0,3}, then b_{1} would be 1 (the first bit of s_{1}) XOR'd with 0 (the last bit of s_{1}), which is 1. Given n, k, and the strings s_{1},...,s_{n} and their corresponding b_{i}, find a set S of size at most k which produces the given b_{i}. You should also detect when no such S exists.
Input
The first line contains n and k, spaceseparated (1 ≤ n ≤ 64, 0 ≤ k ≤ 10). n lines then follow, where the ith line contains s_{i}, followed by a space, then b_{i}. In a given test case all strings s_{i} are of the same length m (1 ≤ m ≤ 50). k will not be bigger than m.
Output
If no set S of size at most k exists producing the given b_{i}, output 1 followed by a newline. Otherwise, on the first line output the size of a possible S. If the size of that S is not 0, on the second line, output a spaceseparated list of the indices in S, followed by a newline. If there exist multiple valid S to be output, you can output any one of your choosing.
Example
Input: 3 1 111 1 001 0 011 1 Output: 1 1
hide comments
Scape:
20160730 23:30:36
Thanks guys! 

Francky:
20160720 14:29:27
Issue fixed, and rejudge in progress ; thanks @admins.


Scape:
20160718 01:11:08
Please fix Internal Error and rejudge all submissions. Thanks!


One Two Three:
20150622 15:45:31
I got Internal Error submitting the solution, please fix it! 

Marcel Stockli:
20120412 21:24:23
somebody has problems with the case 33? I always got WA in that case. 
Added by:  Minilek 
Date:  20081222 
Time limit:  5s30s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  MIT Individual Contest 2008 