#1534. [POI2005]Sum- Fibonacci sums

题目描述

Fibbonacci 数列是这样定义的: Fib0 = 1, Fib1 = 1, Fibi = Fibi-2 + Fibi-1 (for i >= 2). 数列的前几项是: (1, 1, 2, 3, 5, 8,...). 任意一个整数都可以表示为若干个不同的Fib数的和,但为了保证表示的唯一性,我们用 (b1, b2,..., bn) 表示数b1 . Fib1 + b2 . Fib2 + ... + bn . Fibn. (我们没有用Fib0.). 并且有如下规定: · 如果 n > 1, 则 bn = 1, 即表示的数没有前导0. · 如果 bi = 1, 那么 bi+1 = 0 (for i = 1,..., n - 1), 即表示中不· 存在连续的两个0. 给出两个数的Fib表示,求他们的和的Fib表示.

输入格式

第一行一个整数N表示第一个数的Fib表示长度,接下来N个数字0或者1. 第二行和第一行格式相同描述第二个数, 1 <= n <= 1 000 000.

输出格式

一个整数n代表输入的两个数的和的Fib表示的长度,接下来n个数代表表示方案, 1 <= n <= 1 000 000.

样例

样例输入

样例输出

数据范围与提示