

 Task: Fibonacci sumsFibbonacci numbers are an integer sequence defined in the following way: Fib_{0} = 1, Fib_{1} = 1, Fib_{i} = Fib_{i2} + Fib_{i1} (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 Fibbonacci system i.e. a bit string (b_{1}, b_{2},..., b_{n}) denotes the number b_{1}^{ . }Fib_{1} + b_{2}^{ . }Fib_{2} + ^{ ... } + b_{n}^{ . }Fib_{n}. (Note that we do not use Fib_{0}.) Unfortunatelly, 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:
TaskWrite a programme which:
InputThe input contains the Fibbonacci represantations (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 positive 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.
OutputIn the first and only line of the output your programme should write the Fibbonacci representation (satisfying the aforementioned conditions) of the sum x + y. The representation should be in the form of a sequence of positive 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.
Print friendly version 