Fibonacci numbers are an integer sequence defined in the following way: $\text{Fib}_0=1, \text{Fib}_1=1$, $\text{Fib}_i=\text{Fib}_{i-2}+\text{Fib}_{i-1}$ (for $i ≥ 2$). The first few numbers in this sequence are: (1,1,2,3,5,8,…).
The great computer scientist Byteazar is constructing an unusual computer, in which numbers are represented in Fibonacci system i.e. a bit string $(b_1,b_2,…,b_n)$ denotes the number $b_1⋅\text{Fib}_1+b_2⋅\text{Fib}_2+…+b_n⋅\text{Fib}_n$. (Note that we do not use $\text{Fib}_0$.) Unfortunately, such a representation is ambiguous i.e. the same number can have different representations. The number 42, for instance, 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 very reason, Byteazar has limited himself to only using representations satisfying the following conditions:
- if $n > 1$, then $b_n=1$, i.e. the representation of a number does not contain leading zeros.
- if $b_i=1$, then $b_{i+1}=0$ (for $i=1,…,n-1$), i.e. the representation of a number does not contain two (or more) consecutive ones.
The construction of the computer has proved more demanding than Byteazar supposed. He has difficulties implementing addition. Help him!
Write a programme which:
- reads from the standard input the representations of two positive integers,
- calculates and writes to the standard output the representation of their sum.
Input
The input contains the Fibonacci representations (satisfying the aforementioned conditions) of two positive integers $x$ and $y$ - one in the first, the other in the second line. Each of these representations is in the form of a sequence of non-negative integers, separated by single spaces. The first number in the line denotes the length of the representation $n$, $1 ≤ n ≤ 1\,000\,000$. It is followed by $n$ zeros and/or ones.
Output
In the first and only line of the output your programme should write the Fibonacci representation (satisfying the aforementioned conditions) of the sum $x+y$. The representation should be in the form of a sequence of non-negative integers, separated by single spaces, as it has been described in the Input section. The first number in the line denotes the length of the representation $n$, $1 ≤ n ≤ 1\,000\,000$. It is followed by n zeros and/or ones.
Example
Input
4 0 1 0 1 5 0 1 0 0 1
Output
6 1 0 1 0 0 1