Do You Get the Message?

input file: message.in

In this problem we will be using a one-bit error-correcting code called a Hamming code, which allows the receiver to correct any one-bit error in a binary sequence called a   transmission string. The transmission string is generated by the sender from a binary sequence called the message string, and additional embedded bits called parity bits.

Let us number the transmission string bit positions from left to right starting at 1. The embedded parity bits p₀, p₁, p₂,... p_i,... p_n are at positions 1, 2, 4,... 2i... 2n respectively, where 2n < length(transmission string). Associated with each parity bit p _iis a subset s_i of transmission string bits. Note that p_i is a member of subset s_i. Note also that these subsets are non-disjoint. The value of the parity bits are set so that the parity (sum) of all the bits in their corresponding subset is even. The implied subsets are most easily explained by giving an example: a transmission string bit at position 13 = 11012=1 x 23+ 1 x 22+ 0 x 21+ 1 x 20 = 23+ 22+ 20 contributes to the parity of subsets s₃, s₂ and s₀.

For example, if the message is 10110, the transmission string will be laid out like

• To make the parity of s₀ (bits at positions 1,3,5,7,9) even, p₀ is set to 0.
• To make the parity of s₁ (bits at positions 2,3,6,7) even, p₁ is set to 1.
• To make the parity of s₂ (bits at positions 4,5,6,7) even, p₂ is set to 0.
• To make the parity of s₃ (bits at positions 8,9) even, p₃ is set to 0.

Thus, the generated transmission string—called a Hamming code—will be 011001100, and the sender now transmits this.

We will assume that, if an error occurs during transmission, no more than one bit in the received transmission string will be in error (i.e., inverted).   The receiver checks the parity of each subset.   If s_i is even (i.e., correct), assign a bit b_i a value of 0, otherwise a value of 1. If the binary number corresponding to b_n...b_i...b₂ b₁ b₀   is zero, there were no errors in the transmission, otherwise, the binary number corresponds to the location of the error.

Going back to the example above, let us say that (unbeknown to the receiver) bit 5 was corrupted (inverted), i.e., the received transmission string is 011011100.

The receiver calculates the subset parities, and calculates the error position.

b₀ = 1 (s_o is odd)

b₁ = 0 (s₁ is even)

b₂ = 1 (s₂ is odd)

b₃ = 0 (s₃ is even)

The receiver discovers that the received transmission string bit at position b₃ b₂ b₁ b₀ = 0101₂ = 5 is in error. Thus, the corrected transmission string is 011001100. The (corrected) message string is 10110, obtained by stripping out the parity bits.

Input

The input contains a number of received binary transmission strings, one to a line, that are valid Hamming codes with no more than 1 error (3 <= length of string <32,000). The list is terminated with a transmission string of "0", which is not to be processed.

Output

The (corrected) binary message string is to be output, one to a line.

Sample Input

011011100
011001100
01101
0

Output corresponding to the Sample Input

10110
10110
11