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.
In this system, a number b_k...b_2b_1b_0, where each b_i is either 0 or 1, is considered the (-2)-ary representation of a number n if it satisfies the equation n = b_k * (-2)^k + ... + b_2 * (-2)^2 + b_1 * (-2)^1 + b_0 * (-2)^0.
To help his students grasp the concept, Chin Pu presented them with his favorite puzzle: He writes a sequence A of length n on the board, consisting of zeros and ones (which may include leading zeros). The students are then tasked with writing a sequence B of the same length, also consisting of zeros and ones (and possibly with leading zeros), such that the sum of the (-2)-ary numbers X and Y, represented by sequences A and B respectively, results in the maximum number of ones in its (-2)-ary representation. The sequence B that achieves this is called a valid solution to the puzzle.
Among all valid solutions, Chin Pu wants to find the "maximum" one, meaning the sequence that represents the largest (-2)-ary number.
Given that solving this puzzle can be quite complex for larger values of n, and Chin Pu needs to check his students' solutions, he requests your help in writing a program to solve the puzzle as described.
Input
A string representing the sequence written by the teacher. The string contains between 1 and 50 characters, each being either '0' or '1'.
Output
A string of the same length as the input string. This string should represent the "maximum" sequence that meets the teacher's criteria.