給定一個長度為 $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 不是迴文。