Bersama dengan takdir yang rumit, Nadeko memiliki sebuah string $s$ yang terdiri dari huruf-huruf kecil. Keinginan terbesarnya adalah membentuk sebuah string $t$ yang memenuhi kondisi berikut:
- $t$ tidak memuat $s$ sebagai subbarisan (subsequence).
- Setiap subbarisan dari $s$ yang tidak sama persis dengan $s$ termuat di dalam $t$ sebagai subbarisan.
Bantulah ia menemukan string $t$ dengan panjang seminimal mungkin. Jika terdapat beberapa string seperti itu, Anda diperbolehkan mencetak yang mana saja.
Masukan
Satu-satunya baris masukan berisi string $s$ ($2 \le |s| \le 10^6$) — string milik Nadeko. Dijamin bahwa $s$ hanya berisi huruf-huruf kecil.
Keluaran
Dalam satu baris, cetak sembarang string $t$ dengan panjang minimal yang memenuhi kondisi persoalan.
Contoh
Masukan 1
aaaa
Keluaran 1
aaa
Masukan 2
bba
Keluaran 2
bab
Catatan
Pada contoh kedua, string bab memuat bb, ba, a, b sebagai subbarisan tetapi tidak memuat bba. Jelas pula bahwa mustahil membentuk barisan valid dengan panjang $2$, sehingga bab adalah salah satu jawaban yang mungkin.