Рабочее место участника

Числа Фибоначчи хорошо известны. Они определяются рекуррентным соотношением:

`F_0\ =\ 0`, `F_1\ =\ 1`, `F_n\ =\ F_{n-1}\ +\ F_{n-2}` для `n\ >\ 1`.

Фибоначчиева система счисления (ФСС) основана на теореме Цеккендорфа, утверждающей, что любое целое положительное число имеет единственное представление вида

`N\ =\ F_{k_1}\ +\ F_{k_2}\ +\ …\ +\ F_{k_r}`, где `F_{k_i}` – числа Фибоначчи, а `k_1\ ">>"\ k_2\ ">>"\ …\ ">>"\ k_r\ ">>"\ 0`.

Здесь `i\ ">>"\ \ j` означает, что `i\ ≥\ j+2`. Целое неотрицательное число можно записать в виде последовательности нулей и единиц:

`N\ =\ (b_m\ b_{m-1}…b_2)_F\ hArr\ N\ =\ sum_{k=2}^m\ b_k\ F_k`, где `b_i\ =\ 1`, если `F_i` входит в представление, и 0, в противном случае.

Например, `1000000\ =\ 832040\ +\ 121393\ +\ 46368\ +\ 144\ +\ 55` = `F_30\ +\ F_26\ +\ F_24\ +\ F_12\ +\ F_10` или `(1000000)_10=(10001010000000000010100000000)_F`. Эта система счисления напоминает двоичное представление, за исключением того, что в ней никогда не встречаются две 1 подряд. При прибавлении 1 к числу в ФСС возникают два случая. Если младший разряд есть 0, он заменяется на 1 (так как `F_2=1`), в противном случае в двух младших разрядах будет 01, и они заменяются на 10 (так как `F_3\ =\ F_2\ +\ 1`). Затем мы должны заменять набор цифр 011 на 100 (так как `F_n\ =\ F_{n-1}\ +\ F_{n-2}`), до тех пор, пока в строке цифр имеются две рядом стоящие единицы.

Напишите программу для сложения двух чисел в ФСС.

Во входном файле содержатся два неотрицательных целых числа в ФСС, по одному числу в строке. Количество разрядов в числах может быть различным и не превосходит 1000.

В выходной файл вывести результат сложения этих двух чисел также в ФСС.

1010
100

10010