Kieroutuneen kohtalon ohella Nadekolla on pienistä kirjaimista koostuva merkkijono $s$. Hänen suurin toiveensa on muodostaa merkkijono $t$, jolle pätevät seuraavat ehdot:
- $t$ ei sisällä merkkijonoa $s$ alijonona.
- Jokainen merkkijonon $s$ alijono, joka ei ole sama kuin $s$, sisältyy merkkijonoon $t$ alijonona.
Auta häntä löytämään mahdollisimman lyhyt merkkijono $t$. Jos tällaisia merkkijonoja on useita, voit tulostaa niistä minkä tahansa.
Syöte
Syötteen ainoa rivi sisältää merkkijonon $s$ ($2 \le |s| \le 10^6$) — Nadekon merkkijonon. On taattu, että $s$ sisältää vain pieniä kirjaimia.
Tuloste
Tulosta yhdelle riville mikä tahansa mahdollisimman lyhyt merkkijono $t$, joka täyttää tehtävän ehdot.
Esimerkit
Syöte 1
aaaa
Tuloste 1
aaa
Syöte 2
bba
Tuloste 2
bab
Huomautus
Toisessa esimerkissä merkkijono bab sisältää alijonoina merkkijonot bb, ba, a, b, mutta ei sisällä merkkijonoa bba. On myös ilmeistä, että pituuden $2$ kelvollista jonoa on mahdotonta muodostaa, joten bab on mahdollinen vastaus.