「MCOI-03」数据

Rin 正在给 MCOI Round 998244353 的题目出数据。 但是她太菜了，把数据生成器写出锅了，于是数据只生成了一半然后生成器就 RE 了。 现在她想请你用这一半的数据恢复出完整的数据。

以下是一些常见的定义，如果你很熟悉它们你也可以不看。 01 串是指仅包含 ```0``` 和 ```1``` 两种字符的字符串，仅包含其中一种也是可以的。 一个字符串取出其连续的一段称为子串。容易发现一个长度为 $2n$ 的字符串有 $n+1$ 个长度为 $n$ 的子串。 一组实数 $A$ 的平均值 $\overline{A}=\frac{\sum_{x\in A}x}{|A|}$，即所有元素的和除以元素的个数。 在此基础上，$A$ 的方差 $S^2=\frac{\sum_{x\in A}(x-\overline{A})^2}{|A|}$，即所有元素与平均值的差的平方和除以元素的个数。 一个长度为 $n$ 的 01 串 $S$ 的二进制值等于 $\sum_{i=1}^nS_i2^{n-i}$，其中 $S_i$ 是 $S$ 从左向右第 $i$ 个字符上的数字。 在本题中，给出如下定义： 一组数据是一个长度为 $2n$ 的 01 串。 一组数据的毒瘤度定义为，其所有长度为 $n$ 的子串的二进制值的方差。 现在，给定一组数据的前 $n$ 个字符。你需要找到使得这组数据的毒瘤度 **最小** 的后 $n$ 个字符。如果有多解，请按照这后 $n$ 个字符构成的子串的二进制值从小到大排序输出。

输入数据共一行，包含一个长度为 $n$ 的 01 串，表示一组数据的前 $n$ 个字符。

输出若干行，每一行一个长度为 $n$ 的 01 串，表示一组毒瘤度最小的数据的后 $n$ 个字符，按照其二进制值从小到大排序输出。

10

10

#### 样例一解释 在本例中 $n=2$，存在四组满足要求的数据分别是 ```1000```，```1001```，```1010```，```1011```。 ```1010``` 有三个长度为 $2$ 的子串，分别为 ```10```，```01```，```10```。它们的二进制值分别为 $2,1,2$。${2,1,2}$ 的平均值为 $\frac{5}{3}$，方差为 $\frac{2}{9}$。故 ```1010``` 的毒瘤度为 $\frac{2}{9}$。 可以计算出这四组数据的毒瘤度分别为 $\frac{8}{9},\frac{2}{3},\frac{2}{9},\frac{2}{3}$。其中 ```1010``` 是唯一毒瘤度最小的，故程序输出其后 $2$ 个字符 ```10```。 #### 数据范围与提示 保证所有数据随机生成。对于 01 串的每一位，其为 ```1``` 的概率都是 $\frac{1}{2}$ 且不同位相互独立。 本题不采用捆绑测试，按点给分。测试点 $1$ 计 $1$ 分，其他测试点每个计 $3$ 分。 每个测试点 $n$ 的规模如下表： | 测试点编号 | $1$ | $2\sim 7$ | $8\sim 13$ | $14\sim 16$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $n$ | $\le 3$ | $\le20$ | $=26$ | $=56$ | |**测试点编号**|$17\sim 20$ | $21\sim 24$ | $25\sim 28$ | $29\sim 34$ | |$n$|$=200$ | $=500$ | $\le1000$ | $\le 1500$ | 提示：在 C++ 中您可以使用 $128$ 位整数```__int128```。