Cho trước một xâu, bạn muốn sắp xếp lại các kí tự của nó sao cho không có cặp kí tự kề nhau nào giống nhau. Hỏi xâu có thứ tự từ điển nhỏ nhất tạo ra được là bao nhiêu?

Input

Dòng duy nhất chứa xâu độ dài \(n\) chỉ chứa các kí tự trong đoạn \([A-Z]\).

Output

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

Constraints

• \(1≤n≤10^6\)

Example

Sample Input:

HATTIVATTI

AHATITITVT