Junto con un destino retorcido, Nadeko tiene una cadena $s$ que consta de letras minúsculas. Su mayor deseo es construir una cadena $t$ para la cual se cumplan las siguientes condiciones:
- $t$ no contiene a $s$ como subsecuencia.
- Toda subsecuencia de $s$ que no coincida con $s$ está contenida en $t$ como subsecuencia.
Ayúdala a encontrar una cadena $t$ de la menor longitud posible. Si existen múltiples cadenas así, puedes imprimir cualquiera de ellas.
Entrada
Una sola línea de la entrada contiene la cadena $s$ ($2 \le |s| \le 10^6$) — la cadena de Nadeko. Se garantiza que $s$ solo contiene letras minúsculas.
Salida
En una sola línea, imprime cualquier cadena $t$ de longitud mínima que satisfaga las condiciones del problema.
Ejemplos
Entrada 1
aaaa
Salida 1
aaa
Entrada 2
bba
Salida 2
bab
Nota
En el segundo ejemplo, la cadena bab contiene bb, ba, a, b como subsecuencias, pero no contiene bba. También es obvio que es imposible construir una secuencia correcta de longitud $2$, por lo que bab es una respuesta posible.