「PA 2019」斐波那契乘积

题目来源：PA 2019 Runda 3 Iloczyny Fibonacciego

题目描述

定义斐波那契数列为：

• $F_1 = 1$
• $F_2 = 2$
• $F_i = F_{i - 1} + F_{i - 2} \quad (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$