Smart Card Encryption Key Modification

Goran is recovering from knee surgery and is experimenting with smart card encryption keys. In this problem, a key is defined as a binary sequence of length 3n (where n is a positive integer). The positions in the sequence are numbered from 1 to 3n. The weight of a key is defined as

[ \text{weight} = \Bigl(\sum_{i=1}^{3n-1} \mathbf{1}{s_i \neq s_{i+1}}\Bigr) + 1, ]

For example, the weight of "000" is 1, and the weight of "011010100" is 7.

Goran has discovered that he can send small pulse currents to alter the circuitry of the smart card and thus modify the key. Specifically, he may repeatedly perform the following operation:

• Select any two adjacent bits and flip both simultaneously (i.e. change 0 to 1 and 1 to 0).

For instance, with one operation he can change "000" to "110".

Given a key of length 3n, your task is to modify it by performing no more than n operations such that the resulting key has a weight of at least 2n. You may assume that a valid solution always exists.

inputFormat

The input consists of a single line containing a binary string s of length 3n (where n is a positive integer).

outputFormat

Output a binary string of length 3n that can be obtained from s by performing no more than n operations, and whose weight is at least 2n.

sample

000

010