利用计算机计算离散傅里叶变换（DFT）的高效、快速计算方法统称作快速傅里叶变换（Fast Fourier Transform）。 你的青梅竹马最近学习了 FFT 算法，并将两个**系数均为 $0$ 或 $1$ 的多项式 $a$ 和 $b$** 进行了卷积乘法，得到了一个新的多项式 $c$。他（她）将多项式 $c$ 交给了你，如果你能找到原本的两个多项式 $a,b$，满足 $a \ne c,\ b \ne c,\ a \times b = c$ 的话，他（她）这周末就带你去看电影！ - 系数均为 $0$ 或 $1$ 的多项式：若将多项式描述为 $a_0x^0 + a_1x^1 + a_2x^2 + \cdots$，则 $a_i \in \{0,1\}$.

第一行包含一个正整数 $n$ $(2 \le n\le 16)$，表示多项式的最高项次数。 第二行包含 $n+1$ 个非负整数 $c_0, c_1, \cdots, c_n$，其中 $c_i$ 表示多项式 $c$ 的第 $i$ 项的系数。 数据保证存在至少一种符合条件的解。

两行，每行包含 $n+1$ 个整数。 第一行输出 $a_0, a_1, \cdots, a_n$ $(0 \le a_i \le 1)$，其中 $a_i$ 表示多项式 $a$ 的第 $i$ 项的系数。 第二行输出 $b_0, b_1, \cdots, b_n$ $(0 \le b_i \le 1)$，其中 $b_i$ 表示多项式 $b$ 的第 $i$ 项的系数。 如果存在多种解法，输出任意一种即可。

对于样例一： - $x^2+2x+1 = (x+1)(x+1)$ 对于样例二： - $x^3+x^2+x+1 = (x^2+1)(x+1)$

2023-04-16 ZJNU 天梯赛模拟场 L2-1