Bạn được cho một chuỗi có độ dài n, gồm các ký tự in hoa từ A đến Z. Hãy sắp xếp lại các ký tự trong chuỗi sao cho không có hai ký tự liền kề nào giống nhau.

Trong số tất cả các cách sắp xếp thỏa mãn điều kiện, hãy in ra xâu có thứ tự từ điển nhỏ nhất. Nếu không thể tạo được một xâu thỏa mãn, hãy in ra -1.

Đầu vào:

Một dòng duy nhất chứa chuỗi đầu vào, gồm n ký tự in hoa từ ~A~ đến ~Z~.

Đầu vào:

In ra chuỗi thỏa mãn điều kiện và nhỏ nhất theo thứ tự từ điển, hoặc -1 nếu không có cách sắp xếp nào hợp lệ.

Ràng buộc:

~1 \le n \le 10^6~

Ví dụ :

Input:

HATTIVATTI

Output:

AHATITITVT