Quadratic equation#4373
Sign in

Quadratic equation

2 seconds
256 megabytes
Very hard

Children are taught in school to solve quadratic equations, which are equations of the form:

ax^2 + bx + c = 0

where , , and are given real numbers, and is the real number to be determined.

In this problem, you are required to solve a quadratic equation for polynomials with coefficients of zeros and ones, with all operations performed modulo .

Given polynomials , , and , find a polynomial such that:

a(t)x^2(t) + b(t)x(t) + c(t) = 0

where equality is understood as equality of polynomials. Recall that polynomials are equal if and only if their coefficients at corresponding powers of are equal.

Input

The input file contains polynomials , , and , which are provided by their degrees, followed by coefficients starting from the highest. Zero polynomials in this problem have a degree of . The degrees of all polynomials do not exceed . There are two spaces between the highest coefficient and the degree. After a polynomial of degree , there is also one space.

Output

If there is at least one solution to the equation, output any one of them in the same format. The leading coefficient of the found polynomial must not be zero. The degree of the polynomial should not exceed .

Otherwise, print no solution.

Examples

Example 1

Loading
Loading