描述

考虑系数为 0 和 1 的多项式。两个多项式的加法通过对多项式中对应幂次的系数进行“相加”来实现。系数的加法是通过模 2 加法进行的，即$(0 + 0) \bmod 2 = 0$，$(0 + 1) \bmod 2 = 1$，$(1 + 0) \bmod 2 = 1$，以及$(1 + 1) \bmod 2 = 0$。因此，它与异或操作相同。

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

两个多项式的减法也以类似的方式进行。由于系数的减法是通过模 2 减法进行的，而模 2 减法也等同于异或操作，所以多项式的减法与加法相同。

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

两个多项式的乘法以通常的方式进行（当然，系数的加法是通过模 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$

两个多项式$f(x)$和$g(x)$对多项式$h(x)$取模的乘法是$f(x)g(x)$除以$h(x)$的余数。

例如：$(x^6 + x^4 + x^2 + x + 1)(x^7 + x + 1)$ 对$(x^8 + x^4 + x^3 + x + 1)$取模的结果为 $x^7 + x^6 + 1$

多项式中最大的指数称为它的次数。例如，$x^7 + x^6 + 1$的次数是 7。

给定三个多项式$f(x)、g(x)和h(x)$，你需要编写一个程序来计算$f(x)g(x)对h(x)$取模的结果。

我们假设$f(x)和g(x)$的次数都小于$h(x)$的次数。多项式的次数小于 1000。

由于多项式的系数是 0 或 1，一个多项式可以用$d + 1$和一个长度为$d + 1$的位串来表示，其中$d$是多项式的次数，位串表示多项式的系数。例如，$x^7 + x^6 + 1$可以表示为$8\ 1\ 1\ 0\ 0\ 0\ 0\ 0\ 1$。

输入

输入由$T$个测试用例组成。测试用例的数量$T$在输入文件的第一行给出。每个测试用例由三行组成，每行包含一个多项式$f(x)$、$g(x)$和$h(x)$。每个多项式按照上述方式表示。

输出

输出应该包含$f(x)g(x)$对$h(x)$取模的多项式，每行一个。

2 
7 1 0 1 0 1 1 1 
8 1 0 0 0 0 1 1 
9 1 0 0 0 1 1 0 1 1 
10 1 1 0 1 0 0 1 0 0 1 
12 1 1 0 1 0 0 1 1 0 0 1 0 
15 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1

8 1 1 0 0 0 0 0 1 
14 1 1 0 1 1 0 0 1 1 1 0 1 0 0 

来源

大田 2001 年