题目描述

二进制字符串是由 $0$ 和 $1$ 组成的非空序列，例如 $010110$、$1$、$11101$ 等。两个二进制字符串 $S$ 和 $T$ 的编辑距离，记为 $edit(S, T)$，是指通过单字符编辑操作（插入、删除或替换）将 $S$ 修改为 $T$ 所需的最少操作次数。例如，$0011$ 与 $1100$ 的编辑距离为 $4$，即 $0011 \to 011 \to 11 \to 110 \to 1100$。$1100101$ 与 $1110100$ 的编辑距离为 $2$，即 $1100101 \to 1110101 \to 1110100$。

阿玉有一个二进制字符串 $S$。她想找一个与 $S$ 等长的二进制字符串，使得它与 $S$ 的编辑距离最大。形式化地说，她希望找到一个二进制字符串 $T_{max}$，满足 $|S| = |T_{max}|$，并且对于所有满足 $|S| = |T'|$ 的二进制字符串 $T'$，都有 $edit(S, T_{max}) \geq edit(S, T')$。

她需要你的帮助！不过，为了降低你的任务难度，你可以返回任意一个与 $S$ 等长的二进制字符串 $T$，只需满足 $S$ 与 $T$ 的编辑距离大于 $S$ 长度的一半即可。形式化地说，你必须返回一个二进制字符串 $T$，满足 $|S| = |T|$ 且 $edit(S, T) > \frac{|S|}{2}$。

当然，如果你想的话，仍然可以返回 $T_{max}$，因为可以证明对于任意二进制字符串 $S$，都有 $edit(S, T_{max}) > \frac{|S|}{2}$。这也证明了对于任意二进制字符串 $S$，解总是存在的。如果有多个有效解，输出任意一个即可。

输入格式

输入包含一个二进制字符串 $S$（$1 \leq |S| \leq 2000$）。

输出格式

输出一行一个与 $S$ 等长的二进制字符串 $T$，满足 $edit(S, T) > \frac{|S|}{2}$。

0011

1100

1100101

0011010

提示

样例输入 #1 的解释

如上述示例所示，$0011$ 与 $1100$ 的编辑距离为 $4$。由于 $4 > \frac{4}{2}$，因此 $1100$ 是该样例的一个有效输出。

翻译由 DeepSeek V3.2 完成