Background

As everyone knows, the string problems in the monthly Beginner Contest are all ideas enumerated by Fusu.

Problem Description

Given a 01 string $s$, you may choose any non-empty substring of $s$ and reverse this substring once within $s$.

What is the lexicographically smallest string you can obtain?

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

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

Minimize the lexicographic order of string $t$.

Input Format

The input contains only one line with a string, representing $s$.

Output Format

Output one line with a string, representing the lexicographically smallest string that can be obtained.

101

011

0010100

0000101

Hint

Explanation for Sample 1

$s = \texttt{\underline{10}1}$. Reverse the underlined substring to get $t = \texttt{011}$.

Explanation for Sample 2

$s = \texttt{00\underline{10100}}$. Reverse the underlined substring to get $\texttt{0000101}$.

Constraints

Let $|s|$ denote the length of the input string.

• For $100\%$ of the testdata, $1 \leq |s| \leq 3000$. $s$ contains only characters $\texttt{0,1}$.

Translated by ChatGPT 5