Teacher's Brain-Teaser

A math teacher at one of Japan's top schools, Chin Pu, introduced his students to the $(-2)$-ary numeral system.

Recall that a number b_k\ldots b_2 b_1 b_0, where b_i = 0 or b_i = 1 for any $i$, is called the $(-2)$-ary representation of a number $n$ if it satisfies the equation n = b_k \cdot (-2)^k + \ldots + b_2 \cdot (-2)^2 + b_1 \cdot (-2)^1 + b_0 \cdot (-2)^0.

To reinforce the material, Chin Pu gave his favorite puzzle to the students: he writes a sequence $A$ of length $n$ on the board, consisting of zeros and ones (possibly with leading zeros), and asks the students to write underneath it a sequence $B$ of length $n$, also consisting of zeros and ones (possibly with leading zeros), such that the sum of the $(-2)$-ary numbers $X$ and $Y$ represented by $A$ and $B$ has the maximal possible number of ones in its $(-2)$-ary representation. Such a sequence $B$ is called a valid solution to the puzzle.

Among all valid solutions, Chin Pu asks to find the "maximum" one, meaning the one representing the greatest $(-2)$-ary number.

Because for sufficiently large $n$ the puzzle can be rather complex, and Chin Pu needs to check the correctness of his students' solutions, he asks you to write a program that solves the puzzle as described above.