PARITY - Parity

You are given n binary strings s1 ... sn, each of the same length m. Along with each si you are given a bit bi. You are also given some nonnegative integer k and want to know whether there exists a subset S of {0, 1 ... m-1} of size at most k such that for each i = 1, 2 ... n, the bit bi is the XOR of the bits of si at the indices in S. The si are 0-indexed 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 s1 = 1010 and S = {0, 3}, then b1 would be 1 (the first bit of s1) XOR'd with 0 (the last bit of s1), which is 1. Given n, k, and the strings s1 ... sn and their corresponding bi, find a set S of size at most k which produces the given bi. You should also detect when no such S exists.

Input

The first line contains n and k, space-separated (1 ≤ n ≤ 64, 0 ≤ k ≤ 10). n lines then follow, where the ith line contains si, followed by a space, then bi. In a given test case all strings si 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 bi, 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 space-separated 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

Added by:Minilek
Date:2008-12-22
Time limit:5s-30s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT Individual Contest 2008

hide comments
2021-06-20 13:39:21
1. This problem shows WA after all case(33) , even your 1st case is wrong.
2. You can't print space after last element of elements.
3. In case of zero elements, Don't print multiple newlines. Print just one newline.
2016-07-30 23:30:36 Scape
Thanks guys!
2016-07-20 14:29:27 Francky
Issue fixed, and rejudge in progress ; thanks @admins.
(Edit) => Done.

Last edit: 2016-07-21 17:59:49
2016-07-18 01:11:08 Scape
Please fix Internal Error and rejudge all submissions. Thanks!

=(Francky)=> Mail send to admins ; please be patient.

Last edit: 2016-07-18 13:33:24
2015-06-22 15:45:31 One Two Three
I got Internal Error submitting the solution, please fix it!
2012-04-12 21:24:23 Marcel Stockli
somebody has problems with the case 33? I always got WA in that case.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.