Sumy Fibonacciego

Limit pamięci: 32 MB

Liczby Fibonacciego to ciąg liczb całkowitych zdefiniowany następująco: , , (dla ). Oto kilka pierwszych wyrazów tego ciągu: .

Wielki informatyk Bajtazar konstruuje niezwykły komputer. Liczby w tym komputerze są reprezentowane w układzie Fibonacciego. Liczby w takim układzie są reprezentowane jako ciągi zer i/lub jedynek (bitów), ciąg reprezentuje liczbę . (Zwróć uwagę, że nie korzystamy z ). Taka reprezentacja liczb nie jest niestety jednoznaczna, tzn. tę samą liczbę można reprezentować na wiele sposobów. Na przykład, liczbę można reprezentować jako: , lub . Dlatego też Bajtazar ograniczył się wyłącznie do reprezentacji spełniających następujące warunki:

• jeżeli , to , czyli reprezentacja liczby nie zawiera wiodących zer,
• jeżeli , to (dla ), czyli reprezentacja liczby nie zawiera dwóch (lub więcej) jedynek obok siebie.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia reprezentacje dwóch dodatnich liczb całkowitych,
• obliczy i wypisze reprezentację ich sumy na standardowe wyjście.

Wejście

Na wejściu znajdują się reprezentacje Fibonacciego (spełniające podane powyżej warunki) dwóch dodatnich liczb całkowitych i - jedna w pierwszym, a druga w drugim wierszu. Każda z tych reprezentacji jest zapisana jako ciąg nieujemnych liczb całkowitych, pooddzielanych pojedynczymi odstępami. Pierwsza liczba w wierszu to długość reprezentacji , . Po niej następuje zer i/lub jedynek.

Wyjście

W pierwszym i jedynym wierszu wyjścia, Twój program powinien wypisać reprezentację Fibonacciego (spełniającą podane powyżej warunki) sumy . Tak jak to opisano dla wejścia, reprezentacja powinna mieć postać ciągu nieujemnych liczb całkowitych, pooddzielanych pojedynczymi odstępami. Pierwsza liczba w wierszu to długość reprezentacji , . Po niej następuje zer i/lub jedynek.

Przykład

Dla danych wejściowych:

4 0 1 0 1
5 0 1 0 0 1

poprawną odpowiedzią jest:

6 1 0 1 0 0 1

Autor zadania: Marcin Kubica.