#3219. 「PA 2019」Iloczyny Fibonacciego

内存限制:768 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 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