Description

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.

Input Format

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

Output Format

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.

10

10

Hint

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:

Note: In C++, you can use the $128$-bit integer __int128.

Translated by ChatGPT 5