题目背景

翻译自 CSES-1743 题。

题目描述

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

输入格式

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

输出格式

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

样例

HATTIVATTI

AHATITITVT

说明/提示

$1 \leq n \leq 10^6$。