Prefix Reversal 3

You are given a string S of length N. For each integer i from 1 through N, in that order, you may choose whether to reverse exactly the first i characters of the current string.

After all choices have been made, output the lexicographically smallest string that can be obtained.

The first line contains the string S.

The length of S is at most 50, and every character is an uppercase English letter.

Print the lexicographically smallest obtainable string.