Sammen med enfloket skjebne har Nadeko en streng $s$ som består av små bokstaver. Hennes største ønske er å konstruere en streng $t$ der følgende betingelser gjelder:
- $t$ inneholder ikke $s$ som en delsekvens.
- Enhver delsekvens av $s$ som ikke sammenfaller med $s$, er inneholdt i $t$ som en delsekvens.
Hjelp henne med å finne en streng $t$ av kortest mulig lengde. Hvis det finnes flere slike strenger, kan du skrive ut hvilken som helst.
Inndata
En enkelt linje i inndataene inneholder strengen $s$ ($2 \le |s| \le 10^6$) — Nadekos streng. Det er garantert at $s$ kun inneholder små bokstaver.
Utdata
På en enkelt linje skal du skrive ut en hvilken som helst streng $t$ av minimal lengde som oppfyller betingelsene i oppgaven.
Eksempler
Inndata 1
aaaa
Utdata 1
aaa
Inndata 2
bba
Utdata 2
bab
Merk
I det andre eksemplet inneholder strengen bab delsekvensene bb, ba, a, b, men inneholder ikke bba. Det er også åpenbart at det er umulig å konstruere en gyldig sekvens med lengde $2$, så bab er et mulig svar.