Polish version    English version  
  History of OI


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN

Task: Fibonacci sums

Fibbonacci numbers are an integer sequence defined in the following way: Fib0 = 1, Fib1 = 1, Fibi = Fibi-2 + Fibi-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 Fibbonacci system i.e. a bit string (b1, b2,..., bn) denotes the number b1 . Fib1 + b2 . Fib2 + ... + bn . Fibn. (Note that we do not use Fib0.) 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:

  • if n > 1, then bn = 1, i.e. the representation of a number does not contain leading zeros.
  • if bi = 1, then bi+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!

Task

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 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.

Output

In 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