Minimizing the Variance of Binary Substrings

Given a fixed-length binary prefix of length n, complete it to a full binary string of length 2n by choosing the last n characters. The full string is considered as a data set. In this data set, consider all n+1 contiguous substrings of length n (the first substring is the given prefix, the last substring is exactly the chosen extension, and the others overlap between the prefix and the extension). Each substring is interpreted as a binary number (with the leftmost bit having weight \(2^{n-1}\) and the rightmost \(2^0\)).

The tumor level of the data set is defined as the variance of these n+1 binary numbers. In particular, if the set of numbers is \(\{b_0, b_1, \dots, b_n\}\) then their mean is \[ \overline{b}=\frac{\sum_{i=0}^{n}b_i}{n+1}, \] and the variance is \[ S^2=\frac{1}{n+1}\sum_{i=0}^{n}(b_i-\overline{b})^2. \] Since only the relative order matters, you can minimize the value \[ F=(n+1)\sum_{i=0}^{n}b_i^2 - \left(\sum_{i=0}^{n}b_i\right)^2, \] which is equivalent to minimizing the variance.

Your task is: Given the first n characters (a binary string) as the prefix, find all possible binary strings of length n that can serve as the suffix so that the tumor level (i.e. the variance defined above) is minimized. If there are multiple solutions, output them in increasing order of their binary value (when interpreted as an integer). The output should list each valid suffix on a new line.

inputFormat

The input consists of a single line containing a binary string S of length n (\(1 \leq n \leq 16\), for example). This string is the fixed prefix of the full data set.

outputFormat

Output all valid binary strings of length n (one per line) which, when appended to the prefix, minimize the tumor level of the full \(2n\)-length string. The outputs must be sorted in ascending order based on their integer value (when interpreted as binary numbers).

sample

101

101