Ásamt flóknum örlögum á Nadeko streng $s$ sem samanstendur af lágstöfum. Hennar æðsta ósk er að smíða streng $t$ sem uppfyllir eftirfarandi skilyrði:
- $t$ inniheldur ekki $s$ sem hlutrunu.
- Sérhver hlutruna í $s$ sem er ekki alveg eins og $s$ er innihaldin í $t$ sem hlutruna.
Hjálpaðu henni að finna streng $t$ af minnstu mögulegu lengd. Ef fleiri en einn slíkur strengur er til máttu prenta hvern sem er þeirra.
Inntak
Eina lína inntaksins inniheldur strenginn $s$ ($2 \le |s| \le 10^6$) — streng Nadeko. Tryggt er að $s$ inniheldur eingöngu lágstafi.
Úttak
Prentaðu í einni línu hvaða streng $t$ sem er af lágmarkslengd sem uppfyllir skilyrði verkefnisins.
Dæmi
Inntak 1
aaaa
Úttak 1
aaa
Inntak 2
bba
Úttak 2
bab
Athugasemd
Í seinna dæminu inniheldur strengurinn bab hlutrunurnar bb, ba, a, b en inniheldur ekki bba. Það er líka augljóst að ómögulegt er að smíða rétta runu af lengd $2$, svo bab er mögulegt svar.