Dada una cadena $S$ de longitud $N$ y una cadena vacía $R$, obtenga la cadena $R$ resultante tras repetir el siguiente proceso hasta que $S$ esté vacía:
- Eliminar el primer carácter de $S$ y añadirlo al final de $R$.
- Si $R$ contiene una subcadena palíndroma de longitud $2$ o más, eliminar la más larga de ellas. Si hay varias subcadenas palíndromas de la misma longitud máxima, eliminar la que aparece primero.
- Repetir el paso 2 hasta que no queden subcadenas palíndromas de longitud $2$ o más en $R$.
Entrada
La primera línea contiene la longitud $N$ de la cadena $S$. $(1 \le N \le 500\,000)$
La segunda línea contiene la cadena $S$ compuesta únicamente por letras minúsculas del alfabeto inglés.
Salida
La primera línea debe imprimir la cadena $R$ resultante tras aplicar todo el proceso descrito. Si $R$ está vacía después de aplicar todos los pasos, imprima -1 en su lugar.
Ejemplos
Entrada 1
5 abaaa
Salida 1
-1
Entrada 2
4 dimi
Salida 2
d
Nota
Una cadena $A$ se denomina subcadena de $B$ si $A$ aparece como una parte contigua de $B$. Por ejemplo, di, m y dimi son subcadenas de dimi, pero a, ii y mid no lo son.
Una cadena $A$ se denomina palíndromo si se lee igual de izquierda a derecha que de derecha a izquierda. Por ejemplo, a, sees y racecar son palíndromos, pero cab, dimi y palindrome no lo son.