Prefikslərin çevrilməsi
İntellektual Prefiks Alqoritmləri Laboratoriyasında (İPAL) Prefiksləri Çevirən Maşın (PÇM) sınaqdan keçirilir. Maşın belə işləyir: giriş olaraq uzunluğu n olan s adlı bir sətir və 1 ≤ a_1 < a_2 < ... < a_k ≤ n ardıcıllığı verilir. Əvvəlcə sətir s maşının xüsusi daxili registrinə yerləşdirilir. Daha sonra hər bir i üçün 1 ilə k arasında maşın cari sətirin [1..a_i] prefiksini götürür və onu çevirir. Maşının işinin sonunda registrdə olan sətir maşının işinin nəticəsini təşkil edir.
Məsələn, əgər maşına giriş olaraq "abacaba" sətiri və a_1=2, a_2=4 ardıcıllığı verilsə, çıxışda "caababa" sətiri alınacaq.
İPAL alimləri verilmiş sətir üçün elə bir ardıcıllıq tapmaq istəyirlər ki, işin nəticəsi leksikoqrafik qaydada mümkün qədər kiçik olsun. α=α_1α_2...α_n sətiri leksikoqrafik olaraq β=β_1β_2...β_m sətirindən kiçikdir, əgər bəzi k üçün və bütün 1 ≤ t ≤ k üçün α_t = β_t və ya α_{k+1} < β_{k+1}, ya da α uzunluğu k bərabərdir və β uzunluğu k-dan böyükdür.
Onlara leksikoqrafik olaraq minimum nəticəni necə əldə edə biləcəklərini tapmağa kömək edin.
Giriş verilənləri
Giriş faylı s sətirini ehtiva edir (o boş deyil və uzunluğu 500000-i keçmir). O, kiçik latın əlifbası hərflərindən ibarətdir.
Çıxış verilənləri
PÇM üçün giriş olaraq verilmiş s sətiri üçün leksikoqrafik olaraq minimum olan sətiri çıxış edin.