Sufiks oyunu#5912
Ksyuşa sətirlərlə oyun oynayır.
Ksyuşa hər dəfə bir hərf olmaqla, ardıcıl olaraq sətirə hərflər əlavə edir. İlk addımda o, s_1 hərfini yazır, ikinci addımda isə s_2 hərfini əlavə edir və bu şəkildə davam edir. Bundan əlavə, Ksyuşanın adlı bir sətiri var və bu sətir vasitəsilə Ksyuşanın oyunda qazandığı xal hesablanır.
Ksyuşanın qazandığı xal aşağıdakı qaydada hesablanır: ilk addımda s_1 sətirinin içindəki daxilolma sayı xallara əlavə olunur. İkinci addımda s_1s_2 sətirinin içindəki daxilolma sayı xallara əlavə olunur. Üçüncü addımda isə s_1s_2s_3 sətirinin içindəki daxilolma sayı xallara əlavə olunur və bu şəkildə davam edir. Əvvəlcə xal sayı -a bərabərdir.
Ksyuşa istədiyi vaxt hərfləri yazmağı dayandıra bilər. Ona oyunda mümkün olan ən çox xalı qazanmaq üçün strategiya seçməyə kömək edin. Başqa sözlə, elə bir s = s_1s_2 \dots s_n sətirini tapın ki, əgər Ksyuşa bu sətirin simvollarını ardıcıllıqla yazsa, mümkün olan ən çox xalı qazansın.
Birinci sətirdə sətiri verilmişdir (1 \leq |t| \leq 10^4). sətiri yalnız kiçik latın hərflərindən ibarətdir.
Cavab olaraq sətirini çıxarın. Əgər belə sətirlər bir neçədərsə, leksikoqrafik ardıcıllıqla ən kiçiyini çıxarın.
Nümunə 1
s = x_1x_2\dots x_p sətiri leksikoqrafik olaraq y = y_1y_2\dots y_q sətirindən kiçikdir, əgər ya p < q və x_1 = y_1, x_2 = y_2, ..., x_p = y_p, və ya elə bir (r < p, r < q) mövcuddur ki, x_1 = y_1, x_2 = y_2, ..., x_r = y_r və x_{r+1} < y_{r+1}. Sətirlərin simvolları onların ASCII kodları ilə müqayisə olunur.