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 \textbf{s} of length \textbf{n} and a sequence \textbf{1} ≤ \textbf{a_1} < \textbf{a_2} < ... < \textbf{a_k} ≤ \textbf{n}. Initially the string \textbf{s} is put to the internal register of the machine. After that for each \textbf{i} from \textbf{1} to \textbf{k} the machine takes the prefix \textbf{\[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 \textbf{s} = "\textbf{abacaba}" and \textbf{a_1} = \textbf{2}, \textbf{a_2} = \textbf{4}, the output of the machine is "\textbf{caababa}". The LIPA scientists want to find output what is the lexicographically minimal string that can be the output of the machine on input \textbf{s}. Help them to find that out. \InputFile The input file contains a string \textbf{s} (its length doesn't exceed \textbf{500000}). It contains only lowercase letters. \OutputFile Output the smallest lexicographically string that can be the output of the RPM on input \textbf{s}.