Prefikslərin çevrilməsi

Ağıllı Prefiks Alqoritmləri Laboratoriyasında (APA) Prefiks Geriçevirmə Maşını (PGM) sınaqdan keçirilir. Maşının iş prinsipi belədir: ona $s$ uzunluğunda bir sətir və 1 \leq a_1 < a_2 < \ldots < a_k \leq n ardıcıllığı verilir. Əvvəlcə sətir $s$ maşının xüsusi daxili registrinə yerləşdirilir. Sonra isə hər $i$ üçün $1$-dən $k$-ya qədər maşın cari sətirin [1..a_i] prefiksini götürür və onu geri çevirir. Maşın işini bitirdikdən sonra registrdə olan sətir maşının işinin nəticəsi hesab olunur.

Məsələn, əgər maşının girişinə $\text{abacaba}$ sətiri və ardıcıllıq a_1 = 2, a_2 = 4 verilsə, çıxış sətiri $\text{caababa}$ olacaq.

APA alimləri verilmiş sətir üçün elə bir ardıcıllıq tapmaq istəyirlər ki, maşının işinin nəticəsi lüğəvi ardıcıllığa görə mümkün olan ən kiçik sətir olsun. \alpha = \alpha_1\alpha_2 \ldots \alpha_n sətiri \beta = \beta_1\beta_2 \ldots \beta_m sətirindən lüğəvi ardıcıllığa görə kiçikdir, əgər elə bir $k$ mövcuddur ki, 1 \leq t \leq k üçün həmişə \alpha_t = \beta_t və ya \alpha_{k+1} < \beta_{k+1}, yaxud da $\alpha$-nın uzunluğu $k$-ya bərabərdir və $\beta$-nın uzunluğu $k$-dan böyükdür.

Sizdən xahiş olunur ki, bu maşında verilməsi nəticəsində alınacaq mümkün ən kiçik lüğəvi ardıcıllıqlı sətiri tapın.