Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2700
Quadratic Equation

Time Limit: 10 Seconds      Memory Limit: 32768 KB      Special Judge

Children in school learn how to solve quadratic equations --- that is, equations of form


where a , b and c are some given real numbers, and x is the real number to find.

In this problem you have to solve quadratic equation for polynomials with coefficients from Z/2Z . Recall, that there are two numbers in Z/2Z : 0 and 1 , and all operations in this field are performed modulo 2 .

Given polynomials a(t) , b(t) and c(t) , find such polynomial x(t) that


where equality should be considered as polynomial equality. Remember, that two polynomials are equal if and only if their coefficients at corresponding powers of t are equal.


There are mutilple cases in the input file.

Each case contains a(t) , b(t) and c(t) , specified as their power followed by their coefficients, starting from the leading one (the coefficient at the greatest power of t ). Zero polynomial has the degree of -1 for the purpose of this problem. Degrees of all polynomials do not exceed 127 .

There is an empty line after each case.


If there is at least one solution to the equation, output any one in the same format, that is used in input. Leading coefficient of the answer polynomial must not be zero. The degree of the polynomial must not exceed 512.

In the other case print “no solution” on the first line of the output file.

There should be an empty line after each case.

Sample Input

0  1
2  1 1 0
3  1 0 0 0 

0  1
1  1 1
0  1


Sample Output

1  1 0

no solution


In the first example the equation has the form


and x(t) = t is clearly a solution.

In the second example the equation is


and there is no solution.

In the third example the equation is 0 = 0 and any polynomial is a solution.

Source: Andrew Stankevich's Contest #9
Submit    Status