Seeding The Pattern

All submissions for this problem are available.
The Chef has decided to take a break from the restaurant. Rather than sitting on some boring tropical beach for hours on end, he has decided to join an archaeological dig. His latest discovery is an ancient tablet containing a list of numbers that seem to fit some pattern. At the top of the list are d numbers a_{0}, ..., a_{d1}, each of which is either 0 or 1. The rest of the list is only partially readable, but it seems to contain an extremely long list of 0/1 numbers x_{0}, x_{1}, ...
Only some of the x_{i} values are readable and the rest are too damaged to make out. The Chef conjectures that these numbers fit the following pattern. For any number n ≥ 0, the Chef conjectures that x_{n+d} = a_{0}x_{n} + ... + a_{d1}x_{n+d1}. Because of the nature of this pattern, he is calling the first d integers x_{0}, ..., x_{d1} the "seeds". Finally, this ancient civilization appears to be only concerned about whether a number is odd or even. Because of this, his conjecture is that the numbers fit the previous pattern when all results are reduced modulo 2.
Your job is to help the Chef determine the validitiy of his conjecture. Specifically, you are to determine if there is a way to assign either a 0 or a 1 to all unreadable x_{i} entries so that the pattern holds. If so, you must determine if there is more than one way to do this or if there is exactly one way to do this. If there is exactly one way, you must specify the values of the "seeds".
Input
The first line contains a single integer indicating the number of test cases to follow (at most 50). Each test case begins with two integers d and k. The next line contains the d values a_{0}, ..., a_{d1} that are written at the top of the tablet. Finally, k lines follow where the j'th line contains two integers i(j) and x_{. This specifies the value of the readable number xi(j). The ij values will appear in strictly increasing order.}
Bounds: Both d and k are between 1 and 20. All values a_{i} and x_{i(j)} are either 0 or 1. Finally, each index i(j) is between 0 and 2^{31}1.
Output
The output for each test case is a single line containing one of three messages. If there is no way to fill in the missing values x_{i} so that the pattern holds, then you should output "no solutions". If there are multiple ways to assign values to the missing x_{i} so that the pattern holds, then output "multiple solutions".
Finally, if there is only one way to assign values to the missing x_{i} values, then you should output a line containing the d values x_{0}, ..., x_{d1} with a single space between consecutive numbers. Since these values are calculated modulo 2, then they are either 0 or 1.
Example
Input: 3 2 2 1 1 0 0 2 1 2 2 1 1 0 0 3 0 2 2 1 0 0 0 2 1 Output: 0 1 multiple solutions no solution
Author:  friggstad 
Tester:  rajivka 
Editorial  http://discuss.codechef.com/problems/SEEDS 
Tags  cook05, friggstad, medium 
Date Added:  8122010 
Time Limit:  1.13 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions