Reversing Prefixes
A reversing prefixes machine (RPM) is being tested in Laboratory of Intelligent Prefixes Algorithms (LIPA). The machine works in the following way: the input to it is a string s of length n and a sequence 1 ≤ a_1 < a_2 < ... < a_k ≤ n. Initially the string s is put to the internal register of the machine. After that for each i from 1 to k the machine takes the prefix [1..a_i] of the string that is in the register and reverses it. The string that is in the register after all operations are completed is the output of the machine.
For example, if the input to the machine is s = "abacaba" and a_1 = 2, a_2 = 4, the output of the machine is "caababa".
The LIPA scientists want to find output what is the lexicographically minimal string that can be the output of the machine on input s. Help them to find that out.
Input
The input file contains a string s (its length doesn't exceed 500000). It contains only lowercase letters.
Output
Output the smallest lexicographically string that can be the output of the RPM on input s.