Étant donné une chaîne de caractères $S$ de longueur $N$ et une chaîne vide $R$, déterminez la chaîne $R$ obtenue après avoir répété le processus suivant jusqu'à ce que $S$ soit vide :
- Supprimez le premier caractère de $S$ et ajoutez-le à la fin de $R$.
- Si $R$ contient une sous-chaîne palindrome de longueur au moins $2$, supprimez la plus longue d'entre elles de $R$. S'il existe plusieurs sous-chaînes palindromes de longueur maximale, supprimez celle qui apparaît le plus tôt dans $R$.
- Répétez l'étape 2 jusqu'à ce qu'il n'y ait plus de sous-chaîne palindrome de longueur au moins $2$ dans $R$.
La première ligne contient la longueur $N$ de la chaîne $S$. $(1 \le N \le 500\,000)$
La deuxième ligne contient la chaîne $S$ composée uniquement de lettres minuscules de l'alphabet anglais.
Affichez la chaîne $R$ obtenue après avoir appliqué toutes les étapes décrites. Si $R$ est vide après avoir appliqué toutes les étapes, affichez -1 à la place.
Exemples
Entrée 1
5 abaaa
Sortie 1
-1
Entrée 2
4 dimi
Sortie 2
d
Remarque
Une chaîne $A$ est appelée une sous-chaîne de $B$ si $A$ apparaît comme une partie contiguë de $B$. Par exemple, di, m et dimi sont des sous-chaînes de dimi, mais a, ii et mid ne le sont pas.
Une chaîne $A$ est appelée un palindrome si elle se lit de la même manière de gauche à droite et de droite à gauche. Par exemple, a, sees et racecar sont des palindromes, mais cab, dimi et palindrome ne le sont pas.