長さ $N$ の文字列 $S$ と空の文字列 $R$ が与えられる。$S$ が空になるまで以下の過程を繰り返し適用した後の $R$ を求めよ。
- $S$ の先頭の文字を削除し、その文字を $R$ の末尾に追加する。
- $R$ に長さ $2$ 以上の回文である部分文字列が存在する場合、その中で最も長いものを $R$ から削除する。もし最も長い回文部分文字列が複数存在する場合は、その中で最も先頭に近いものを削除する。
- $R$ に長さ $2$ 以上の回文部分文字列が存在しなくなるまで、2番のステップを繰り返す。
入力
1行目に文字列 $S$ の長さ $N$ が与えられる。$(1 \le N \le 500\,000)$
2行目に（英）小文字のみからなる文字列 $S$ が与えられる。
出力
1行目に問題で説明した過程をすべて適用した後の $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 は回文ではない。