Sắp xếp lại xâu

Cho một xâu \(S\) độ dài \(n\) gồm các chữ cái in hoa từ A đến Z. Hãy sắp xếp lại các kí tự của xâu 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 lại hợp lệ, hãy tìm xâu có thứ tự từ điển nhỏ nhất.

\InputFile

• Một dòng duy nhất chứa xâu \(S\) độ dài \(n\) gồm các kí tự A--Z \((1 \le n \le 10^6)\).

\OutputFile

• 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ự liền kề nào giống nhau. Nếu không tồn tại cách sắp xếp nào thoả mãn, in ra \(-1\).

\Examples
\beginexample
\exmp
HATTIVATTI

AHATITITVT

\endexample

\Scoring

• (\(20\%\)) \(1 \le n \le 10\);
• (\(80\%\)) Không có ràng buộc thêm.

\endproblem