This problem was inspired by and is dedicated to our creative gurus - Clive and Mathias.
Edouard Zeckendorf, whom we first met in this eponymous task was not only an able matematician but also biologist and particularly acarologist (the person interested in mites and ticks - small insect-like creatures with 8 legs known for their biting abilities).
Moreover his famous theorem was inspired by study of curious class of ticks, known since then as Zeckendorf Ticks
(in brief Zekes or Zeken). Actually it is not clear, whether they are called after him or vice versa!
Zeckendorf Ticks are haploid quantum creatures, conformant to Pauli exclusion principle (hopefully you are impressed,
feel free to re-read this nonsense). Each Zeke is characterised by its spin, which is an integer number, but
only can have one of special series of values. Smallest ticks have spin 3, next in size have spin 9. Further
every next possible value of spin may be found by multiplied spins of two preceding orders:
3 9 27 243 6561 1594323 ...
Zekes live in colonies, conveniently called Dorfs (e.g. "villages"), obeying to the aforementioned exclusion
principle: there could be no two Zekes with the same spin!
Also there could be no two ticks with spins expressed by consequent values (e.g. 9 and 27 or
6561 and 1594323) but not because of exclusion! Zeken tend to recombine: whensoever it happens that Dorf
includes two creatures with two immediate values of spin - they at once combine to
produce another Zeke with the next spin value in order (effectively, their spin is multiplied).
These processes are quantum in their nature, meaning one can't reliably trace how exclusions and recombinations
happen - only final result is observable. For example, imagine it so happened for a moment, a village of
three Zekes occurred, with spins 3, 9, 27. The first two ticks tend to recombine, but this will bring
situation to violation of Pauli principle (two ticks with spin 27 can't exist in a village) so instead
we conclude Zeken with spins 9 and 27 merge so the final state of a village is just a pair of creatures
with spins 3 and 243.
Problem Statement
There were two Zeken Dorfs on the banks of small rivulet. However, due to global warming, rivulet evaporated one morning and villages are no more separate. Our goal is to figure out the state of the resulting Dorf (e.g. spins of its ticks) after turbulent quantum process of all necessary recombinations is completed.
What exactly happens when in the process of merge two ticks are found with the same spin - it is difficult to tell - however Zekes always resolve such "collision" and, as only result is important, think of it, for example, as if one of the ticks falls apart into two Zeken of preceeding order of spin, then various possible recombinations occur.
Input consists of two descriptions of initial villages, in special form described below. Output should describe the resulting state, in the same special form.
Dorf description format
As Zeken sometimes recombine in the course of evolution, their spins may be expressed by very large values. Hence it is not convenient to write the population of the village simply as a list of such values.
Instead we'll binary notation, with each bit meaning whether corresponding spin value is included or not.
The rightmost bit corresponds to smallest value of 3. For example, the Dorf with Zeke spins of 3, 27, and
10460353203 is written down as 1000101 (where zeroes means, right to left, no ticks with spins 9, 243,
6561 and 1594323).
Input provides the two Dorf descriptions, in the binary format shown above. As they are long, they are
split into lines of convenient length, each ending with a distinct line containing three dashes (---).
Output should give description of resulting combined Dorf as a long binary value.
Example 1
input:
1010000101000001000010000100100001
---
1010010000100010100100010100010
answer:
10000100001001000000000101001010000
Example 2
input:
1001001000100101010100010100001000010001010100010001000101000010010101001000000000000000000001000100
0000101001001000010010010100101000001010010001010100001000000010000010000100100010010101001000010100
1000001000100000010000101000000101000101001001000101010010101000001001001001000010010010010000010100
010000100001010101000001001010000
---
1001000000000000000010010010000000100010101001001010000010100000001000001001000010001010010010010010
0001000101000000100100000001000001001001000101010000010100010010000010001000010000010100000100000010
0000100000000010000010000100001010010000001001010100000010000010100000010010010000000010001010001010
000100101010001010001010000100000
---
answer (also split for convenience):
1010100100010100000000100000000100100010101001000010000101000001010010101010000001000101001010010000
00010010010100001001000100000001010000000100001001010000100010100100101000001000100000010100100100
000100010100010001001010000000001010010000000000000001010101010101010101000010001001001010100101
0101000100000000000101001010000010010000