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]\)

Constraints

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

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

Example

HATTIVATTI

AHATITITVT