Головоломка учителя
Учитель математики одной из лучших школ Японии Тин Пу обучил своих учеников (-2)-ой системе счисления.
Напомним, что число b_k...b_2b_1b_0, где b_i = 0 или b_i = 1 для любых i, называется (-2)-ым представлением числа n, когда имеет место равенство n = b_k * (-2)^k + ... + b_2 * (-2)^2 + b_1 * (-2)^1 + b_0 * (-2)^0.
Для закрепления материала Тин Пу предложил ученикам решить его любимую головоломку, смысл которой заключается в следующем: учитель выписывает на доске последовательность А длины n, состоящую из нулей и единиц (возможно, с лидирующими нулями) и просит учеников выписать под ней последовательность В длины n, также из нулей и единиц (и также, возможно, с лидирующими нулями), такую, что сумма (-2)-ых чисел X и Y, представленных соответственно последовательностями А и В, в своей (-2)-ой записи имела бы максимальное количество единиц. В этом случае последовательность В называется допустимым решением головоломки.
Из всех допустимых решений Тин Пу просит найти "максимальное", то есть то, которое представляет наибольшее (-2)-ое число.
Так как при достаточно больших n решение головоломки довольно трудоёмко, а Тин Пу должен проверять правильность решений своих учеников, он просит Вас написать для него программу, которая будет решать вышеописанную головоломку.
Входные данные
Строка, описывающая последовательность, выписанную учителем. Строка содержит от 1 до 50 символов '0'/'1' включительно.
Выходные данные
Строка той же длины, что и входная строка. Строка должна задавать "максимальную" из последовательностей, удовлетворяющих условию учителя.