Altardizi

Verilmiş $s$ sətirini nəzərə alaraq, $s$ sətirinin alt ardıcıllığı olmayan ən qısa sətiri tapmalısınız. Əgər belə sətirlər bir neçədirsə, leksikoqrafik olaraq ən kiçiyini seçin. Əgər yalnız minimal uzunluqlu sətiri tapsanız, yarım bal ala bilərsiniz.

Xatırladaq ki, $a$ sətiri $b$ sətirinin alt ardıcıllığıdır, əgər $b$ sətirindən bəzi (bəlkə də heç biri və ya hamısı) simvolları silməklə $a$ sətirini əldə edə bilsək.

$a$ sətiri leksikoqrafik olaraq $b$ sətirindən kiçikdir, əgər aşağıdakı iki şərtdən biri yerinə yetirilirsə:

• $a$, $b$-nin prefiksidir, amma $a\ne b$;

• $a$ və $b$ fərqləndiyi ilk mövqedə, $a$ sətirində əlifbada $b$-dəki müvafiq hərfdən əvvəl gələn bir hərf var.

Giriş verilənləri

Birinci sətir $s$ sətirini ehtiva edir ($1\le |s|\le 10^5$).

Çıxış verilənləri

Sətiri çıxarın.

Nümunələr

Qeyd

Qeyd edək ki, sətirdə bütün mümkün simvollar mövcuddur və sətir «a» ilə başlayır və bitir.

Bütün mümkün simvollar mövcud olduğuna görə, cavab $1$ ola bilməz. İlk «a» hərfindən sonra bütün digər hərflər olduğuna görə, cavabın ilk simvolu ən azı «b» olacaq. «ba» alt sətiri var, amma «bb» yoxdur, buna görə cavab «bb»-dir.

Əgər bu test qiymətləndirilsəydi, «bb» çıxarsaydınız $2$ bal alardınız. Əgər uzunluğu $2$ olan başqa bir sətir çıxarsaydınız (məsələn, «aa», «ba», «zz»), $1$ bal alardınız.

Qiymətləndirmə

Bu məsələdə $50$ test olacaq, hər biri $2$ balla qiymətləndirilir. Əgər testdə düzgün cavab çıxarsanız, $2$ bal alacaqsınız.

Əgər çıxardığınız sətir cavabla eyni uzunluqda olarsa, $1$ bal alacaqsınız. Bu sətir yalnız kiçik ingilis əlifbası hərflərindən ibarət olmalıdır. Qeyd edək ki, bu sətir üçün başqa heç bir tələb yoxdur. Yəni, hətta $s$-nin alt ardıcıllığı olan bir sətir çıxara bilərsiniz. Əsas odur ki, uzunluq cavabla eyni olsun.