Polynomial Remainder Operation

Consider a special set of polynomials whose coefficients are all either 0 or 1. Addition, subtraction, and multiplication on this set are all defined by reducing each resulting coefficient modulo 2.

Addition. Add the two polynomials in the usual way, then reduce every coefficient modulo 2. Since $(0+0)\bmod 2=0$, $(0+1)\bmod 2=1$, $(1+0)\bmod 2=1$, and $(1+1)\bmod 2=0$, each coefficient of the result is the XOR of the corresponding coefficients of the two operands.

$(x^6 + x^4 + x^2 + x + 1) + (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2$

Subtraction. Likewise $(0-0)\bmod 2=0$, $(0-1)\bmod 2=1$, $(1-0)\bmod 2=1$, and $(1-1)\bmod 2=0$, so on this set subtraction is identical to addition (coefficient-wise XOR).

$(x^6 + x^4 + x^2 + x + 1) - (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2$

Multiplication. Multiply the two polynomials in the usual way, then reduce every coefficient modulo 2.

$(x^6 + x^4 + x^2 + x + 1)(x^7 + x + 1) = x^{13} + x^{11} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + 1$

Remainder. The remainder of the product of $f(x)$ and $g(x)$ divided by $h(x)$ is obtained by first forming $f(x)g(x)$ as above and then taking its remainder upon division by $h(x)$.

$(x^6 + x^4 + x^2 + x + 1)(x^7 + x + 1) \bmod (x^8 + x^4 + x^3 + x + 1) = x^7 + x^6 + 1$

Notation. Let $d$ be the degree of a polynomial's highest term. Because every coefficient is 0 or 1, the polynomial is uniquely described by the integer $d+1$ together with a bit string of length $d+1$. The bit string lists the coefficients from the highest-degree term down to the constant term. Every polynomial has degree less than 1000.

For example, $x^7 + x^6 + 1$ is written as:

8 1 1 0 0 0 0 0 1

Here 8 is the total number of bits, equal to the highest degree 7 plus 1. The following 8 bits 1 1 0 0 0 0 0 1 are the coefficients of $x^7, x^6, x^5, x^4, x^3, x^2, x^1, x^0$ respectively.

Given three polynomials $f(x)$, $g(x)$, and $h(x)$ in this format, compute the remainder of $f(x)g(x)$ divided by $h(x)$.

The input consists of several test cases.

The first line contains the number of test cases $T$. Each test case then spans three lines giving $f(x)$, $g(x)$, and $h(x)$, in that order, in the format described above.

For each test case, print on one line the remainder of $f(x)g(x)$ divided by $h(x)$, in the format described above. If the remainder is the zero polynomial, print it as 1 0.