伟大的计算机科学家 Bajtazar 已经研究了一种不同寻常的计算机超过 15 年，在这种计算机中，数字以斐波那契系统表示，即表示为若干互不相邻的斐波那契数之和。

形式上，如果我们定义斐波那契数列，从 1 和 2 开始： $F_1 = 1, F_2 = 2, F_i = F_{i-1} + F_{i-2}$，对于 $i \ge 3$，

那么每个正整数 $x$ 都可以唯一地表示为一个比特序列 $(b_1, b_2, \dots, b_n)$（对于某个 $n \ge 1$），满足以下条件： $x = b_1 \cdot F_1 + b_2 \cdot F_2 + \dots + b_n \cdot F_n$； $b_i \in \{0, 1\}$，对于所有 $1 \le i < n$，且 $b_n = 1$（仅包含 0 和 1，无前导零）； * $b_i \cdot b_{i+1} = 0$，对于所有 $1 \le i < n$（不存在两个相邻的 1）。

例如，$2 = (0, 1)$，$4 = (1, 0, 1)$，$5 = (0, 0, 0, 1)$，而 $20 = (0, 1, 0, 1, 0, 1)$，因为 $20 = F_2 + F_4 + F_6 = 2 + 5 + 13$。

很久以前，Bajtazar 曾请求信息学奥林匹克竞赛的参赛者帮助实现斐波那契系统下的加法。这个故事发生在第 XII 届波兰信息学奥林匹克竞赛（OI）第二阶段的“斐波那契和”题目中，并被记录在奥赛的“蓝色小册子”中。

这一次问题更难了，Bajtazar 已经为此苦思冥想了好几年。因此，他决定向“算法竞赛”（Potyczki Algorytmiczne）的参赛者寻求建议。请帮他实现乘法！

输入格式

输入的第一行包含测试用例的数量 $t$ ($1 \le t \le 1000$)。接下来的 $2t$ 行描述了这些测试用例。

每个测试用例由两行组成。第一行给出了正整数 $x$ 在斐波那契系统下的表示——首先是表示其长度的数字 $n$，然后是 $n$ 个比特 $b_1, b_2, \dots, b_n$。 第二行以相同的格式给出了正整数 $y$ 的表示。

输入中所有表示的长度之和不超过 $10^6$。

输出格式

对于输入中的每个测试用例，输出乘积 $x \cdot y$ 在斐波那契系统下的表示，格式与输入相同——首先是长度 $n'$，然后是目标数字的 $n'$ 个比特。行内的各个数字应以单个空格分隔。

输入和输出的表示必须满足题目中的条件，特别是比特序列必须以 1 结尾，且不能包含相邻的 1。

样例

输入 1

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

输出 1

6 0 1 0 1 0 1
2 0 1

说明 1

在第一个测试用例中，我们需要将由序列 $(1, 0, 1)$ 和 $(0, 0, 0, 1)$ 表示的数字相乘。展开后我们得到： $(1 \cdot F_1 + 0 \cdot F_2 + 1 \cdot F_3) \cdot (0 \cdot F_1 + 0 \cdot F_2 + 0 \cdot F_3 + 1 \cdot F_4) = (1 + 3) \cdot (5) = 20 = F_2 + F_4 + F_6$ 因此结果是长度为 6 的序列 $(0, 1, 0, 1, 0, 1)$。

子任务

存在一组测试，其中输入中的每个序列仅包含一个 1 ($b_n = 1$)。此外还存在另一组测试，其中每个测试中所有 $2t$ 个序列中的 1 的总数不超过 2000。