题目描述

给定一个字符串，你需要重新排列它的字符，使得相邻的字符不相同。求这样的字符串中字典序最小的排列。

输入格式

唯一的输入行是一个长度为 n 的字符串，字符串由大写字母 A–Z 组成。

输出格式

输出一个字典序最小的重排字符串，使得相邻的字符不相同。如果无法生成这样的字符串，输出 −1。

样例

输入数据 1

HATTIVATTI

输出数据 1

AHATITITVT

说明/提示

1≤n≤10⁶。