给定定义在有限域 $\mathbb{Z}/2\mathbb{Z}$ 上的多项式 $f(x)$，$g(x)$ 和 $h(x)$。

求多项式 $f(g(x)) \bmod h(x)$。

输入格式

输入的前三行分别包含多项式 $f$，$g$ 和 $h$，每行一个。每个多项式 $p$ 的描述格式为 $n\ p_0\ p_1\ p_2\ \dots\ p_n$（其中 $1 \le n \le 4000$，对于所有 $i$ 有 $p_i \in \{0, 1\}$，且 $p_n = 1$）。多项式 $p(x)$ 等于 $p_0 + p_1x + p_2x^2 + \dots + p_nx^n$。

输出格式

以相同的格式输出结果多项式。

如果答案是零多项式，则输出 0 0。

样例

输入样例 1

5 0 1 0 1 0 1
2 1 1 1
4 0 1 1 0 1

输出样例 1

1 1 1

输入样例 2

2 1 1 1
3 0 0 1 1
4 1 0 1 0 1

输出样例 2

3 1 0 0 1

说明

我们来回顾一些定义。

有限域 $\mathbb{Z}/2\mathbb{Z}$ 是一个包含两个元素 $0$ 和 $1$ 的集合，其中加法、减法、乘法和除法的结果是普通整数对应运算结果模 $2$ 的余数。

该域上的多项式 $f(x)$ 是形如 $f_n \cdot x^n + f_{n-1} \cdot x^{n-1} + \dots + f_1 x + f_0$ 的表达式，其中系数 $f_n, \dots, f_0$ 是来自 $\mathbb{Z}/2\mathbb{Z}$ 的整数，变量 $x$ 也可以取 $\mathbb{Z}/2\mathbb{Z}$ 中的值。满足 $f_n \ne 0$ 的最大整数 $n$ 称为多项式 $p(x)$ 的次数（degree）。

若对于所有 $k$，$a_k$ 和 $b_k$ 都相等，则多项式 $a(x) = \sum_k a_k x^k$ 和 $b(x) = \sum_k b_k x^k$ 相等。

多项式的加法和减法是逐项进行的：$a(x) \pm b(x) = \sum_k (a_k \pm b_k) \cdot x^k$。

多项式 $a(x)$ 和 $b(x)$ 的乘积为 $c(x) = \sum_k c_k x^k$，其中 $c_s = \sum_{t=0}^s (a_t \cdot b_{s-t})$。

多项式之间可以进行除法。对于非零多项式 $b(x)$，如果满足 $q(x) \cdot b(x) + r(x) = a(x)$ 且 $r(x)$ 的次数严格小于 $b(x)$ 的次数，我们称 $a(x)/b(x) = q(x)$ 且 $a(x) \bmod b(x) = r(x)$。可以证明 $q(x)$ 和 $r(x)$ 是唯一确定的。

复合多项式 $a(b(x))$ 是多项式 $\sum_k a_k (b(x))^k$，其中多项式的幂通过乘法定义：$(b(x))^0 = 1$，$(b(x))^1 = b(x)$，对于 $p > 1$ 有 $(b(x))^p = b(x) \cdot (b(x))^{p-1}$。为了求出系数，展开表达式并将相同 $x$ 幂次的系数相加。