Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
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

ax2+bx+c=0,

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

a(t)x2(t)+b(t)x(t)+c(t)=0,

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.

Input

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.

Output

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

-1
-1
-1

Sample Output

1  1 0

no solution

-1

In the first example the equation has the form

x(t)2+(t2+t)x(t)+t3=0,

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

In the second example the equation is

x(t)2+(t+1)x(t)+1=0,

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