Prefix Reversal 3

Time limit2sMemory limit128 MB

Summary

Given a string, for each prefix length from 1 to N in order you may choose to reverse that prefix, and you must output the lexicographically smallest string achievable after all choices.

Level: Medium6 of 10
Topics: String, Greedy, Dynamic programming, Recursion
Solved: No attempts yet

Problem

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.

Input

The first line contains the string S.

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

Output

Print the lexicographically smallest obtainable string.

Examples3

Example 1
Input
```
BCDAF
```
Expected output
```
ABCDF
```
Example 2
Input
```
ABBA
```
Expected output
```
AABB
```
Example 3
Input
```
ACAB
```
Expected output
```
AACB
```