Given a string $S$ of length $N$ and an empty string $R$, find the final state of $R$ after repeating the following process until $S$ becomes empty:

1. Remove the first character of $S$ and append it to the end of $R$.
2. If there is any palindromic substring of length $2$ or greater in $R$, remove the longest one. If there are multiple longest palindromic substrings, remove the one that appears earliest in $R$.
3. Repeat step 2 until there are no palindromic substrings of length $2$ or greater in $R$.

The first line contains the length $N$ of the string $S$. $(1 \le N \le 500\,000)$

The second line contains the string $S$ consisting only of lowercase English letters.

Print the final string $R$ after applying all the described processes. If $R$ is empty after all processes are complete, print -1 instead.

Examples

Input 1

5
abaaa

Output 1

-1

Input 2

4
dimi

Output 2

d

Note

A string $A$ is a substring of $B$ if $A$ appears as a contiguous sequence in $B$. For example, di, m, and dimi are substrings of dimi, but a, ii, and mid are not.

A string $A$ is a palindrome if it reads the same forwards and backwards. For example, a, sees, and racecar are palindromes, but cab, dimi, and palindrome are not.