Ломиголовка вчителя

Вчитель математики з однієї з найкращих шкіл Японії, Чін Пу, познайомив своїх учнів із $(-2)$-ковою системою числення.

Нагадаємо, що число b_k...b_2b_1b_0, де b_i = 0 або b_i = 1 для будь-якого $i$, називається $(-2)$-ковим представленням числа $n$, якщо виконується рівність n = b_k \cdot (-2)^k + ... + b_2 \cdot (-2)^2 + b_1 \cdot (-2)^1 + b_0 \cdot (-2)^0.

Щоб закріпити матеріал, Чін Пу дав учням свою улюблену задачу: він записує на дошці послідовність $A$ довжини $n$, яка складається з нулів і одиниць (можливо з початковими нулями), і просить учнів записати під нею послідовність $B$ довжини $n$, що також складається з нулів і одиниць (можливо з початковими нулями), таку, щоб сума $(-2)$-кових чисел $X$ і $Y$, представлених $A$ і $B$, мала максимальну можливу кількість одиниць у своєму $(-2)$-ковому представленні. Така послідовність $B$ називається коректним розв'язком задачі.

Серед усіх коректних розв'язків Чін Пу просить знайти "максимальний", тобто такий, що представляє найбільше $(-2)$-кове число.

Оскільки для достатньо великих $n$ задача може виявитися досить складною, а Чін Пу потрібно перевіряти правильність розв'язків учнів, він просить вас написати програму, яка б вирішувала цю задачу, як описано вище.