eolymp
bolt
Try our new interface for solving problems
Problems

Reversing Prefixes

Reversing Prefixes

Time limit 1 second
Memory limit 64 MiB

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 1a_1 < a_2 < ... < a_kn. 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 data

The input file contains a string s (its length doesn't exceed 500000). It contains only lowercase letters.

Output data

Output the smallest lexicographically string that can be the output of the RPM on input s.

Examples

Input example #1
abacaba
Output example #1
aaaabcb
Author Andrew Stankevich
Source Andrew Stankevich Contest 32, Petrozavodsk Summer Training Camp, Wednesday, September 3, 2008