Suffiks oyunu (Çətin)
Kseniya hərflərlə oyun oynayır.
O, hər dəfə bir hərf olmaqla, kağıza yazır. İlk addımda s_1 hərfini, ikinci addımda isə s_2 hərfini yazır və bu qayda ilə davam edir. Kseniya'nın həmçinin t adlı bir sətiri var və bu sətir vasitəsilə oyunda qazandığı xal hesablanır.
Kseniya'nın qazandığı xallar aşağıdakı qaydada hesablanır: Birinci addımda s_1 sətirinin t daxilində neçə dəfə göründüyü qədər xal qazanır. İkinci addımda s_1s_2 sətirinin t daxilində neçə dəfə göründüyü qədər xal qazanır. Üçüncü addımda isə s_1s_2s_3 sətirinin t daxilində neçə dəfə göründüyü qədər xal qazanır və bu şəkildə davam edir. Başlanğıcda xal sayı 0-a bərabərdir.
Kseniya istədiyi vaxt hərfləri yazmağı dayandıra bilər. Ona oyunda maksimum xal əldə etməyə kömək edəcək strategiyanı seçməyə yardım edin. Başqa sözlə, elə bir s_1s_2... s_n sətirini tapın ki, əgər Kseniya bu sətirin simvollarını yazarsa, o, mümkün olan maksimum xal sayını əldə etsin.
Giriş verilənləri
Birinci sətirdə t sətiri verilir (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 sətirini çıxarın. Əgər belə sətirlər bir neçədirsə, leksikoqrafik qaydada ən kiçiyini çıxarın.