题目描述

题目译自 PA 2019 Runda 3 Iloczyny Fibonacciego

定义斐波那契数列为 $F_1 = 1, F_2 = 2, F_i = F_{i - 1} + F_{i - 2} ( i \ge 3)$。

对于任意一个正整数 $x$，我们总能将 $x$ 写成唯一的斐波那契表示 $(b_1, b_2, \ldots, b_n)$，满足：

1. $b_1 \cdot F_1 + b_2 \cdot F_2 + \dots + b_n \cdot F_n = x$。
2. 对于任意的 $i$（$1 \le i < n$）都有 $b_i = 0$ 或 $b_i = 1$；对于 $b_n$ 有 $b_n = 1$。
3. 对于任意的 $i$（$1 \le i < n$）都有 $b_i \cdot b_{i+1} = 0$。

比如 $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$。

给定两个斐波那契表示的正整数 $A$ 和 $B$，请输出 $A \cdot B$ 的斐波那契表示。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数。

每组测试数据包含两行，分别描述 $A$ 和 $B$ 的斐波那契表示。每行首先是一个正整数 $n$，然后 $n$ 个非负整数 $b_1, b_2, \ldots, b_n$。

输出格式

对于每组数据输出一行，按照输入格式输出 $A \cdot B$ 的斐波那契表示。

样例

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

6 0 1 0 1 0 1
2 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$$

数据范围与提示

$1 \le T \le 1000$，输入数据保证所有的 $n$ 加起来不超过 $10^6$。