题目描述
定义斐波那契数列为 F1=1,F2=2,Fi=Fi−1+Fi−2(i≥3)。
对于任意一个正整数 x,我们总能将 x 写成唯一的斐波那契表示 (b1,b2,...,bn),满足:
- b1×F1+b2×F2+...+bn×Fn=x。
- 对于任意的 i(1≤i<n) 都有 bi=0 或 bi=1;对于 bn 有 bn=1。
- 对于任意的 i(1≤i<n) 都有 bi×bi+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×B 的斐波那契表示。
输入格式
第一行包含一个正整数 T,表示测试数据的组数。
每组测试数据包含两行,分别描述 A 和 B 的斐波那契表示。每行首先是一个正整数 n,然后 n 个非负整数 b1,b2,...,bn。
输出格式
对于每组数据输出一行,按照输入格式输出 A×B的斐波那契表示。
提示
对于 100% 的数据,1≤T≤103,输入数据保证所有的 n 加起来不超过 106。