Cho một xâu $S$ có độ dài $N$ và một xâu rỗng $R$. Hãy tìm xâu $R$ sau khi thực hiện lặp lại quy trình sau cho đến khi $S$ trở nên rỗng:

1. Xóa ký tự đầu tiên của $S$ và thêm ký tự đó vào cuối $R$.
2. Nếu $R$ chứa xâu con là palindrome có độ dài từ $2$ trở lên, hãy xóa xâu con dài nhất trong số đó khỏi $R$. Nếu có nhiều xâu con palindrome dài nhất, hãy xóa xâu con xuất hiện sớm nhất (có vị trí bắt đầu nhỏ nhất).
3. Lặp lại bước 2 cho đến khi $R$ không còn xâu con palindrome nào có độ dài từ $2$ trở lên.

Dữ liệu vào

Dòng đầu tiên chứa độ dài $N$ của xâu $S$. $(1 \le N \le 500\,000)$

Dòng thứ hai chứa xâu $S$ chỉ bao gồm các chữ cái tiếng Anh viết thường.

Dữ liệu ra

Dòng đầu tiên in ra xâu $R$ sau khi đã áp dụng tất cả các quy trình được mô tả. Nếu $R$ rỗng sau khi thực hiện xong tất cả các bước, hãy in ra -1.

Ví dụ

Dữ liệu vào 1

5
abaaa

Dữ liệu ra 1

-1

Dữ liệu vào 2

4
dimi

Dữ liệu ra 2

d

Ghi chú

Một xâu $A$ được gọi là xâu con của xâu $B$ nếu $A$ xuất hiện như một phần liên tiếp trong $B$. Ví dụ, di, m, dimi là các xâu con của dimi, nhưng a, ii, mid không phải là xâu con của dimi.

Một xâu $A$ được gọi là palindrome nếu đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Ví dụ, a, sees, racecar là các palindrome, nhưng cab, dimi, palindrome không phải là palindrome.