長さ $N$ の文字列 $S$ と空の文字列 $R$ が与えられる。$S$ が空になるまで以下の過程を繰り返し適用した後の $R$ を求めよ。

1. $S$ の先頭の文字を削除し、その文字を $R$ の末尾に追加する。
2. $R$ に長さ $2$ 以上の回文である部分文字列が存在する場合、その中で最も長いものを $R$ から削除する。もし最も長い回文部分文字列が複数存在する場合は、その中で最も先頭に近いものを削除する。
3. $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 は回文ではない。