Insieme a un destino contorto, Nadeko ha una stringa $s$ composta da lettere minuscole. Il suo desiderio supremo è costruire una stringa $t$ per la quale valgano le seguenti condizioni:
- $t$ non contiene $s$ come sottosequenza.
- Ogni sottosequenza di $s$ che non coincide con $s$ è contenuta in $t$ come sottosequenza.
Aiutala a trovare una stringa $t$ della minima lunghezza possibile. Se esistono più stringhe di questo tipo, puoi stamparne una qualsiasi.
Input
Un'unica riga dell'input contiene la stringa $s$ ($2 \le |s| \le 10^6$) — la stringa di Nadeko. È garantito che $s$ contenga solo lettere minuscole.
Output
In una singola riga, stampa una qualsiasi stringa $t$ di lunghezza minima che soddisfi le condizioni del problema.
Esempi
Input 1
aaaa
Output 1
aaa
Input 2
bba
Output 2
bab
Note
Nel secondo esempio, la stringa bab contiene bb, ba, a, b come sottosequenze ma non contiene bba. È anche ovvio che è impossibile costruire una sequenza corretta di lunghezza $2$, quindi bab è una risposta possibile.