题目描述

定义斐波那契数列为 $F_1=1,F_2=2,F_i=F_{i-1}+F_{i-2}(i\ge 3)$。 对于任意一个正整数 $x$，我们总能将 $x$ 写成唯一的斐波那契表示 $(b_1,b_2,...,b_n)$，满足：

1. $b_1\times F_1+b_2\times F_2+...+b_n\times 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\times b_{i+1}=0$。

比如 $2=(0,1),4=(1,0,1),5=(0,0,0,1),20=(0,1,0,1,0,1)=F[2]+F[4]+F[6]=2+5+13$。

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

输入格式

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

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

输出格式

对于每组数据输出一行，按照输入格式输出 $A\times 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

提示

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