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

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!

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