Maximizing Ordered Pairs in a Binary String

You are given a binary string s consisting only of characters 0 and 1. You are allowed to perform the following operation any number of times:

Choose an index \( i \) (\(1 \le i < n\)) and flip both \(s_i\) and \(s_{i+1}\). The flipping operation is defined as \(0\) becomes \(1\) and \(1\) becomes \(0\). In other words, each chosen adjacent pair \((s_i, s_{i+1})\) is replaced with \((1-s_i, 1-s_{i+1})\).

Your goal is to maximize the number of ordered pairs \((i,j)\) such that \(i < j\) and \(s_i < s_j\). Since \(s_i < s_j\) if and only if \(s_i=0\) and \(s_j=1\), the objective is to maximize the count of such \(0-1\) pairs.

Key Observation: The allowed operation preserves the parity of the number of ones. That is, if the initial string has \(c\) ones, then after any operations the number of ones \(k\) in the final string must satisfy \(k \equiv c \; (\bmod\; 2)\). The maximum number of valid pairs for a fixed \(k\) is \((n-k)\times k\) (i.e. when all 0's come before all 1's). Therefore, you need to choose the value \(k\) (with \(0 \le k \le n\) and \(k \equiv c \; (\bmod\; 2)\)) that maximizes \((n-k)\times k\), and output the corresponding arrangement: a string with \(n-k\) zeros followed by \(k\) ones.

Note: The input string length is \(n\) and the initial count of ones is \(c\). Your task is to output the optimal string configuration that can be achieved under the parity invariant.

inputFormat

The input consists of a single line containing the binary string s (containing only characters 0 and 1).

\(1 \le |s| \le 10^5\)

outputFormat

Output a single line representing the rearranged binary string which maximizes the number of ordered pairs \((i,j)\) such that \(s_i = 0\) and \(s_j = 1\). This string should be composed of some number of 0's followed by some number of 1's, where the count of 1's is chosen to maximize \((n-k) \times k\) and satisfy \(k \equiv c \; (\bmod\; 2)\).

sample

01

01