Задача №111587. Фибоначчи

Числа Фибоначчи - элементы числовой последовательности, в которой каждое последующее число равно сумме двух предыдущих чисел. Более формально, последовательность чисел Фибоначчи {Fn} задается линейным рекуррентным соотношением:

F1 = 1, F2 = 2, Fn = Fn - 1 + Fn - 2, n ≥ 2

Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы весами являются не степени двойки 1,2,4,8,16,..., а числа Фибоначчи 1,2,3,5,8,13,.... В этой системе счисления каждое положительное целое число единственным образом представляется в виде строки нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.

Даны две строки, представляющие натуральные числа A и B. Найти строку, представляющую число A+B.

Входные данные

Даны две строки, представляющие A и B, состоящие из нулей и единиц. Длина каждой из строк не превышает 104.

Выходные данные

Выведите строку, представляющую число A + B. Обратите внимание, что она должна начинаться с единицы.

Примеры тестов

Входные данные
10101
100
Выходные данные
100010

Примечание

Исходные строки '10101' и '100' представляют числа 8 + 3 + 1 = 12 и 3. Ответом является строка '100010', представляющая строку 13 + 2 = 15 = 12 + 3.

Сдать: для сдачи задач необходимо войти в систему