Fibonacci Representation Addition

The Fibonacci numbers are defined by the formulas \(Fib_1 = 1\), \(Fib_2 = 2\), and for \(i \ge 3\), \(Fib_i = Fib_{i-1} + Fib_{i-2}\). Thus the sequence starts as \(1,2,3,5,8,13,21,34,55,...\).

A bit string \((b_1, b_2, \dots, b_n)\) represents the number \[ N = b_1 \cdot Fib_1 + b_2 \cdot Fib_2 + \cdots + b_n \cdot Fib_n, \] where we do not use \(Fib_0\). Note that the representation is required to satisfy the following conditions:

• If \(n>1\), then \(b_n = 1\) (i.e. no leading zero).
• If \(b_i = 1\), then \(b_{i+1} = 0\) for \(i=1,\dots,n-1\) (i.e. no two consecutive ones).

Due to the ambiguity of the Fibonacci representation, only representations obeying the above restrictions are used. For example, the number 42 can be represented as (0,0,0,0,1,0,0,1) among other representations. Byteazar, the great computer scientist, is building a computer that works in the Fibonacci system. However, he is having trouble implementing addition. Your task is to help him by writing a programme which reads the Fibonacci representations (obeying the above restrictions) of two positive integers from the standard input, calculates their sum, and outputs the Fibonacci representation (in the same format) of the sum.

inputFormat

The input consists of two lines. Each line contains a Fibonacci representation of a positive integer. The representation is given as a sequence of bits (0 or 1) separated by spaces. The first bit corresponds to \(Fib_1\), the second to \(Fib_2\), and so on. It is guaranteed that if there is more than one digit, the last digit is 1 and that there are no two consecutive ones.

outputFormat

Output a single line containing the Fibonacci representation of the sum of the two numbers. The output should also be a sequence of bits (0 or 1) separated by spaces, following the same rules.

sample

1
1

0 1