Dany jest ciąg znaków $S$ o długości $N$ oraz pusty ciąg znaków $R$. Wyznacz końcową postać $R$ po wielokrotnym zastosowaniu poniższego procesu, aż ciąg $S$ stanie się pusty:
- Usuń pierwszy znak z $S$ i dodaj go na koniec $R$.
- Jeśli w $R$ znajduje się podciąg będący palindromem o długości co najmniej $2$, usuń z $R$ jego najdłuższe wystąpienie. Jeśli istnieje kilka takich najdłuższych palindromów, usuń ten, który występuje najwcześniej.
- Powtarzaj krok 2, dopóki w $R$ nie będzie już żadnego podciągu będącego palindromem o długości co najmniej $2$.
W pierwszej linii podana jest długość $N$ ciągu $S$. $(1 \le N \le 500\,000)$
W drugiej linii podany jest ciąg $S$ składający się wyłącznie z małych liter alfabetu angielskiego.
W pierwszej linii wypisz $R$ po zakończeniu wszystkich opisanych operacji. Jeśli po zakończeniu wszystkich kroków $R$ jest pusty, wypisz -1.
Przykład
Wejście 1
5 abaaa
Wyjście 1
-1
Wejście 2
4 dimi
Wyjście 2
d
Uwagi
Ciąg $A$ nazywamy podciągiem ciągu $B$, jeśli $A$ występuje jako spójny fragment w $B$. Na przykład di, m oraz dimi są podciągami dimi, natomiast a, ii oraz mid nie są podciągami dimi.
Ciąg $A$ nazywamy palindromem, jeśli czytany od przodu i od tyłu jest taki sam. Na przykład a, sees oraz racecar są palindromami, natomiast cab, dimi oraz palindrome nie są palindromami.