Problem Background

As is well known, Fusu is responsible for generating ideas for the string problems in the monthly beginner competitions.

Problem Description

Given a binary string \( s \), you can choose any non-empty substring of \( s \) and reverse it once within \( s \).

Determine the lexicographically smallest string that can be obtained.

Formally, you can select an interval \([l, r]\) such that \(1 \leq l \leq r \leq |s|\), and construct a string \( t \) satisfying:

\[ t_i = \begin{cases} s_i, & \text{if } i < l \text{ or } i > r \\ s_{r - (i - l)}, & \text{if } l \leq i \leq r \end{cases} \]

Here, the string indices start from 1.

Minimize the lexicographical order of string \( t \).

Input Format

The input consists of a single line containing the string \( s \).

Output Format

Output a single line containing the lexicographically smallest string obtained.

Sample Input and Output

Sample Input #1

101

Sample Output #1

011

Sample Input #2

0010100

Sample Output #2

0000101

Notes

Sample 1 Explanation

\( s = \texttt{\underline{10}1} \), reversing the underlined substring results in \( t = \texttt{011} \).

Sample 2 Explanation

\( s = \texttt{00\underline{10100}} \), reversing the underlined substring results in \( \texttt{0000101} \).

Data Size and Constraints

Let \( |s| \) denote the length of the input string.

• For \( 20\% \) of the data, \( |s| \leq 2 \).
• For \( 40\% \) of the data, \( |s| \leq 8 \).
• Additionally, \( 10\% \) of the data consists of strings containing only the character \( \texttt{1} \).
• Additionally, \( 10\% \) of the data consists of strings containing only the character \( \texttt{0} \).
• For \( 100\% \) of the data, \( 1 \leq |s| \leq 100 \). The string \( s \) contains only the characters \( \texttt{0,1} \).

见题面 Input 部分

见题面 Output 部分