Suffiks oyunu 2
Ksyuşa sətirlərlə oyun oynayır.
Ksyuşa hər addımda bir hərf olmaqla, kağıza hərflər yazır. İlk addımda s_1 hərfini, ikinci addımda s_2 hərfini və s. yazır. Bundan əlavə, Ksyuşanın t adlı bir sətiri var və bu sətir vasitəsilə Ksyuşanın oyunda qazandığı xallar hesablanır.
Ksyuşanın qazandığı xallar belə hesablanır: Birinci addımda s_1 sətirinin t içindəki daxilolmalarının sayı onun xalına əlavə olunur. İkinci addımda s_1s_2 sətirinin t içindəki daxilolmalarının sayı əlavə olunur. Üçüncü addımda s_1s_2s_3 sətirinin t içindəki daxilolmalarının sayı əlavə olunur və s. Başlanğıcda xal sayı 0-a bərabərdir.
Ksyuşa istədiyi vaxt hərfləri yazmağı dayandıra bilər, lakin ən azı bir hərf yazmalıdır. Ona oyunda əldə edilən xalları minimuma endirəcək strategiyanı seçməkdə kömək edin. Başqa sözlə, elə bir sətir s_1s_2s_3 tapın ki, Ksyuşa bu sətirin simvollarını yazarsa, mümkün olan ən az xalı əldə etsin.
Giriş verilənləri
Birinci sətirdə t sətiri verilib (1 ≤ |t| ≤ 10^5). 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ətir s çıxarın. Əgər belə sətirlər bir neçədirsə, leksikoqrafik sıraya görə ə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) var 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.