给定一个长度为 $N$ 的字符串 $S$ 和一个空字符串 $R$，请在 $S$ 为空之前重复执行以下过程，并求出最终的 $R$。

1. 删除 $S$ 的第一个字符，并将该字符添加到 $R$ 的末尾。
2. （随后）如果 $R$ 中存在长度为 $2$ 或以上的回文子串，则删除其中最长的一个。如果存在多个最长的回文子串，则删除其中最靠前的一个。
3. 重复步骤 2，直到 $R$ 中不再包含长度为 $2$ 或以上的回文子串。

输入格式

第一行给定字符串 $S$ 的长度 $N$。$(1 \le N \le 500\,000)$

第二行给定仅由小写英文字母组成的字符串 $S$。

输出格式

第一行输出执行完所有过程后的 $R$。如果执行完所有过程后 $R$ 为空，则输出 -1。

样例

输入 1

5
abaaa

输出 1

-1

输入 2

4
dimi

输出 2

d

说明

如果字符串 $A$ 是字符串 $B$ 的连续部分，则称 $A$ 为 $B$ 的子串。例如，di、m、dimi 是 dimi 的子串，但 a、ii、mid 不是 dimi 的子串。

如果字符串 $A$ 正读和反读都相同，则称 $A$ 为回文串。例如，a、sees、racecar 是回文串，但 cab、dimi、palindrome 不是回文串。