Nhiệm vụ của bạn là sắp xếp lại các ký tự của một xâu sao cho không có hai ký tự kề nhau nào giống nhau. Xâu nào là xâu có thứ tự từ điển nhỏ nhất thỏa mãn?

Dữ liệu vào

Dòng duy nhất chứa một xâu độ dài ~n~ gồm các ký tự A–Z.

Kết quả

In ra xâu đã sắp xếp lại có thứ tự từ điển nhỏ nhất sao cho không có hai ký tự kề nhau nào giống nhau. Nếu không thể tạo được xâu như vậy, in ra ~-1~.

Giới hạn

• ~1 \le n \le 10^6~

Ví dụ

Dữ liệu vào:

HATTIVATTI

Kết quả:

AHATITITVT