Lexicographically Smallest String by Reversing a Substring

You are given a binary string \(s\) consisting of characters '0' and '1'. You are allowed to choose any non-empty substring of \(s\) and reverse that substring exactly once. The reversal is defined as follows: choose an interval \([l, r]\) with \(1 \le l \le r \le |s|\), and construct a new string \(t\) where

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

Your task is to find the lexicographically smallest string \(t\) that can be obtained by applying the reversal operation at most once. Note that if no reversal can improve the string, you may choose a trivial reversal (i.e. reversing a substring of length 1) so that \(t = s\).

inputFormat

The input consists of a single line containing the binary string \(s\) where \(1 \le |s| \le 10^5\).

outputFormat

Output the lexicographically smallest string that can be obtained as described.

sample

1010

0101