Suffiks oyunu (Çətin)#5942
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 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 daxilində neçə dəfə göründüyü qədər xal qazanır. İkinci addımda s_1s_2 sətirinin daxilində neçə dəfə göründüyü qədər xal qazanır. Üçüncü addımda isə s_1s_2s_3 sətirinin daxilində neçə dəfə göründüyü qədər xal qazanır və bu şəkildə davam edir. Başlanğıcda xal sayı -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\ldots 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.
Birinci sətirdə sətiri verilir (1 \leq |t| \leq 10^5). sətiri yalnız kiçik latın hərflərindən ibarətdir.
Tapşırığın cavabını — sətirini çıxarın. Əgər belə sətirlər bir neçədəirsə, leksikoqrafik qaydada ən kiçiyini çıxarın.
Nümunə 1