Fibonacci Sums

The Fibonacci numbers are an integer sequence defined as follows: $F_0 = 1$, $F_1 = 1$, and $F_i = F_{i-2} + F_{i-1}$ for $i \ge 2$. The first few terms of the sequence are $1, 1, 2, 3, 5, 8, \dots$

The computer scientist Byteazar is building an unusual computer in which numbers are represented in the Fibonacci system: a bit string $(b_1, b_2, \dots, b_n)$ denotes the number $b_1 F_1 + b_2 F_2 + \dots + b_n F_n$. (Note that $F_0$ is not used.) Unfortunately, this representation is not unique: the same number can have several representations. For example, the number $42$ can be written as $(0,0,0,0,1,0,0,1)$, $(0,0,0,0,1,1,1,0)$, or $(1,1,0,1,0,1,1)$. For this reason, Byteazar restricts himself to representations satisfying the following two conditions:

• if $n > 1$, then $b_n = 1$; that is, the representation has no leading zeros.
• if $b_i = 1$, then $b_{i+1} = 0$ (for $i = 1, \dots, n-1$); that is, the representation contains no two (or more) consecutive ones.

Byteazar is having trouble implementing addition. Help him!

Write a program that:

• reads from standard input the representations of two positive integers, and
• computes and writes to standard output the representation of their sum.

The input contains the Fibonacci representations (satisfying the conditions above) of two positive integers $x$ and $y$ — one on the first line, the other on the second line. Each representation is a sequence of non-negative integers separated by single spaces. The first number on the line is the length $n$ of the representation, where $1 \le n \le 1\,000\,000$. It is followed by $n$ zeros and/or ones.

On the only line of output, write the Fibonacci representation (satisfying the conditions above) of the sum $x + y$. The representation must be a sequence of non-negative integers separated by single spaces, as described in the Input section. The first number on the line is the length $n$ of the representation, where $1 \le n \le 1\,000\,000$, followed by $n$ zeros and/or ones.