P7047 "MCOI-03" Data.

Rin is preparing the testdata for MCOI Round 998244353. However, she is too inexperienced and wrote a buggy data generator, so it only generated half of the data and then the generator crashed with RE. Now she wants to ask you to recover the full data using this half of the data.

Below are some common definitions. If you are already familiar with them, you may skip this part. A 01 string is a string that contains only the two characters `0` and `1`. It is also allowed to contain only one of them. Taking a consecutive segment of a string is called a substring. It is easy to see that a string of length $2n$ has $n+1$ substrings of length $n$. The mean value of a set of real numbers $A$ is $\overline{A}=\frac{\sum_{x\in A}x}{|A|}$, that is, the sum of all elements divided by the number of elements. Based on this, the variance of $A$ is $S^2=\frac{\sum_{x\in A}(x-\overline{A})^2}{|A|}$, that is, the sum of squared differences between each element and the mean, divided by the number of elements. The binary value of a 01 string $S$ of length $n$ is $\sum_{i=1}^nS_i2^{n-i}$, where $S_i$ is the digit on the $i$-th character of $S$ from left to right. In this problem, we define the following: A piece of data is a 01 string of length $2n$. The "toxic level" of a piece of data is defined as the variance of the binary values of all its substrings of length $n$. Now, you are given the first $n$ characters of a piece of data. You need to find the last $n$ characters such that the "toxic level" of the whole data is **minimized**. If there are multiple solutions, output them sorted by the binary value of the substring formed by these last $n$ characters, from small to large.

The input contains one line, a 01 string of length $n$, representing the first $n$ characters of a piece of data.

Output several lines. Each line contains a 01 string of length $n$, representing the last $n$ characters of a piece of data with minimum "toxic level". Output them sorted by their binary values in increasing order.

#### Explanation for Sample 1 In this example, $n=2$. There are four pieces of data that satisfy the requirement: `1000`, `1001`, `1010`, `1011`. `1010` has three substrings of length $2$: `10`, `01`, `10`. Their binary values are $2,1,2$. The mean of ${2,1,2}$ is $\frac{5}{3}$, and the variance is $\frac{2}{9}$. Therefore, the "toxic level" of `1010` is $\frac{2}{9}$. You can compute that the "toxic levels" of these four pieces of data are $\frac{8}{9},\frac{2}{3},\frac{2}{9},\frac{2}{3}$, respectively. Among them, `1010` is the only one with the minimum "toxic level", so the program outputs its last $2$ characters `10`. #### Constraints and Notes It is guaranteed that all testdata are generated randomly. For each bit of the 01 string, the probability of being `1` is $\frac{1}{2}$, and different bits are independent. This problem does not use bundled tests. It is scored by test points. Test point $1$ is worth $1$ point, and each other test point is worth $3$ points. For each test point, the size of $n$ is given in the table below: | Test Point ID | $1$ | $2\sim 7$ | $8\sim 13$ | $14\sim 16$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $n$ | $\le 3$ | $\le20$ | $=26$ | $=56$ | | **Test Point ID** | $17\sim 20$ | $21\sim 24$ | $25\sim 28$ | $29\sim 34$ | | $n$ | $=200$ | $=500$ | $\le1000$ | $\le 1500$ | Note: In C++, you can use the $128$-bit integer `__int128`. Translated by ChatGPT 5