Sufiks oyunu
Ksyuşa sətirlərlə oyun oynayır.
Ksyuşa hər dəfə bir hərf olmaqla, 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 t 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: İlk addımda s_1 sətirinin t içindəki daxilolma sayı xallara əlavə olunur. İkinci addımda s_1s_2 sətirinin t içindəki daxilolma sayı xallara əlavə olunur. Üçüncü addımda isə s_1s_2s_3 sətirinin t içindəki daxilolma sayı xallara əlavə olunur və bu şəkildə davam edir. Əvvəlcə xal sayı 0-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_1s_2...s_n sətirini tapın ki, əgər Ksyuşa bu sətirin simvollarını yazsa, o, mümkün olan ən çox xalı qazansın.
Giriş verilənləri
Birinci sətirdə t sətiri verilmişdir (1 ≤ |t| ≤ 10^4). t sətiri yalnız kiçik latın hərflərindən ibarətdir.
Çıxış verilənləri
Tapşırığın cavabını — s sətirini çıxarın. Əgər belə sətirlər bir neçədirsə, leksikoqrafik ardıcıllıqla ən kiçiyini çıxarın.
Qeyd. x = x_1x_2...x_p sətiri leksikoqrafik olaraq y = y_1y_2...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, ya da elə bir r (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ı kimi müqayisə olunur.