You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

众所周知，每个月入门赛的字符串题都是扶苏来枚举 idea 出出来的。

题目描述

给定一个 01 字符串 $s$，你可以任选 $s$ 的一个非空子串，把这个子串在 $s$ 中翻转一次。

问你能得到字典序最小的字符串是什么？

形式化的，你可以选择一个区间 $[l, r]$ 满足 $1 \leq l \leq r \leq |s|$，构造一个串 $t$ 满足：

这里字符串的下标从 $1$ 开始。

最小化字符串 $t$ 的字典序。

输入格式

输入只有一行一个字符串，表示 $s$。

输出格式

输出一行一个字符串，表示得到的字典序最小的字符串。

101

011

0010100

0000101

提示

样例 1 解释

$s = \texttt{\underline{10}1}$，翻转下划线标出的子串，得到 $t = \texttt{011}$

样例 2 解释

$s = \texttt{00\underline{10100}}$，翻转下划线标出的子串，得到 $\texttt{0000101}$。

数据规模与约定

下面用 $|s|$ 表示输入字符串的长度。

• 对 $20\%$ 的数据，$|s| \leq 2$。
• 对 $40\%$ 的数据，$|s| \leq 8$。
• 另有 $10\%$ 的数据，$s$ 只含字符 $\texttt 1$。
• 另有 $10\%$ 的数据，$s$ 只含字符 $\texttt 0$。
• 对 $100\%$ 的数据，$1 \leq |s| \leq 100$。$s$ 只含字符 $\texttt{0,1}$。