Tillsammans med ett invecklat öde har Nadeko en sträng $s$ som består av små bokstäver. Hennes yttersta önskan är att konstruera en sträng $t$ för vilken följande villkor gäller:
- $t$ innehåller inte $s$ som en delsekvens.
- Varje delsekvens av $s$ som inte sammanfaller med $s$ finns i $t$ som en delsekvens.
Hjälp henne att hitta en sträng $t$ av minsta möjliga längd. Om det finns flera sådana strängar får du skriva ut vilken som helst.
Indata
En enda rad i indata innehåller strängen $s$ ($2 \le |s| \le 10^6$) — Nadekos sträng. Det garanteras att $s$ endast innehåller små bokstäver.
Utdata
Skriv på en enda rad ut valfri sträng $t$ av minimal längd som uppfyller problemets villkor.
Exempel
Indata 1
aaaa
Utdata 1
aaa
Indata 2
bba
Utdata 2
bab
Notering
I det andra exemplet innehåller strängen bab delsekvenserna bb, ba, a, b, men inte bba. Det är också uppenbart att det är omöjligt att konstruera en giltig sekvens av längd $2$, så bab är ett möjligt svar.