Lexicographically Smallest String Formed by Deque Operations

You are given a string \( S \) and an initially empty string \( T \). You can perform the following operations until \( S \) becomes empty:

1. Remove the first character of \( S \) and insert it at the beginning of \( T \) (i.e. front insertion).
2. Remove the first character of \( S \) and insert it at the end of \( T \) (i.e. back insertion).
3. Remove the last character of \( S \) and insert it at the beginning of \( T \) (i.e. front insertion).

Let the final string \( T \) be the result after all characters from \( S \) have been moved. Your task is to determine the lexicographically smallest \( T \) that can be obtained by applying a sequence of the above operations.

Note: When a character is inserted at the beginning of \( T \) (front insertion), it will appear before the characters that have been inserted earlier in the front. In contrast, when a character is appended at the end, the relative order is preserved.

For example, if \( S = \texttt{bac} \), one valid sequence of operations is:

• Remove \( 'b' \) from the front and append it at the end \( \to T = \texttt{b} \) and \( S = \texttt{ac} \).
• Remove \( 'a' \) from the front and insert it at the beginning \( \to T = \texttt{ab} \) and \( S = \texttt{c} \) (since the new character becomes the new first character of \( T \)).
• Remove \( 'c' \) (only character left) and append it at the end \( \to T = \texttt{abc} \).

The lexicographically smallest \( T \) for \( S = \texttt{bac} \) is \( \texttt{abc} \).

inputFormat

The input consists of a single line containing the string \( S \). \( S \) may contain only lowercase letters.

outputFormat

Output the lexicographically smallest string \( T \) that can be obtained.

sample

bac

abc