结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

仓库的一排货架上依次排列着 $n$ 个货位，每个货位上贴着一张标签，标签上印有一个小写字母。沿货架顺序读出所有标签，得到一个长度为 $n$ 的字符串 $s$。

管理员准备把这 $n$ 张标签全部揭下并重新张贴。每张标签恰好使用一次，不得新增也不得丢弃。重新张贴后，要求货架上任意相邻两个货位的标签字母不同。

在所有满足要求的张贴方案中，管理员希望最终得到的字符串字典序最小。请你求出这个字符串；若不存在满足要求的张贴方案，输出 -1。

输入格式

从文件 rearr.in 中读入数据。

• 第一行一个整数 $n$，表示货位数量；
• 第二行一个长度为 $n$ 的字符串 $s$，表示各货位原有的标签字母。

输出格式

输出到文件 rearr.out 中。

输出一行：若存在满足要求的张贴方案，输出字典序最小的那个字符串；否则输出 -1。

样例

5
aaabb

ababa

样例 1 解释

共 $5$ 个货位，三张 a 与两张 b，相邻字母必须不同，因此只能把两种字母交替放置——奇数位均为 a、偶数位均为 b，得到 ababa。

6
aabbcc

abacbc

样例 2 解释

前三位排出 aba 后，剩余 b、c、c 三张标签。第 4 位若填 b，剩下的两张 c 只能放在第 5、6 位且相邻；故第 4 位只此可填 c，第 5、6 位随之依次填 b、c，得到 abacbc。

6
aaaabc

-1

样例 3 解释

串长为 $6$，其中 a 出现 $4$ 次，而相邻字母不同的一串最多容纳 $3$ 张相同的字母，故无法按要求重新张贴。

数据范围

对于所有测试数据，保证：$1 \le n \le 10^5$，$s$ 由小写字母组成。

各测试点的约束如下：

• 特殊性质 A：$s$ 中只含字母 a 和 b。