Task: Fibonacci sums

Fibbonacci numbers are an integer sequence defined in the following way: Fib₀ = 1, Fib₁ = 1, Fib_i = Fib_i-2 + 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 Fibbonacci system i.e. a bit string (b₁, b₂,..., b_n) denotes the number b₁ ^. Fib₁ + b₂ ^. Fib₂ + ^... + b_n ^. Fib_n. (Note that we do not use Fib₀.) 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 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.

Task

• reads from the standard input the representations of two positive integers,
• calculates and writes to the standard output the representation of their sum.

Input

Output

Print friendly version