eolymp
bolt
Try our new interface for solving problems
Məsələlər

Reversing Prefixes

Reversing Prefixes

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 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.

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
abacaba
Çıxış verilənləri #1
aaaabcb
Müəllif Andrew Stankevich
Mənbə Andrew Stankevich Contest 32, Petrozavodsk Summer Training Camp, Wednesday, September 3, 2008