题目内容

某调度台把本班经过的工位收成一串代号。代号只含小写字母。交班时要把这串代号折成下一班使用的短码，规则如下。

设当前字符串长度为 $L$，从左到右记为 $c_1c_2\ldots c_L$。只要 $L\ge 2$，就做一轮折叠。这一轮只看开始时的字符串，按从外到内的顺序配对：第 $1$ 对是 $(c_1,c_L)$，第 $2$ 对是 $(c_2,c_{L-1})$，依此类推，一共 $\lfloor L/2\rfloor$ 对。每一对按下述规则变成至多一个字母，再按配对的先后顺序接成下一轮字符串：

• 两个字母相同，留下这个字母；
• 两个字母在字母表中相邻，这一对直接消失，不留下字母。$a$ 与 $b$ 相邻，$y$ 与 $z$ 相邻；$z$ 与 $a$ 不相邻；
• 其他情况，留下字母表中更靠后的那个字母。

消失的对不占位置，它前后留下的字母直接拼在一起。

若本轮开始时 $L$ 是奇数，正中间的字符 $c_{(L+1)/2}$ 不参与配对，把它放在下一轮字符串的最前面，后面再接各对留下的字母。$L$ 是偶数时没有这样的中间字符。

下一轮用得到的新字符串继续折叠。长度变成 $1$ 或 $0$ 就停止。开始时长度已经是 $1$，则不做折叠。最后若还剩字符串，输出它；若变成空串，输出 $-1$。

输入描述

第一行一个仅由小写字母组成的字符串，表示工位代号。

约束

$1 \le$ 字符串长度 $\le 10^5$

字符串中只含小写字母 $a$ 至 $z$

输出描述

输出折叠结束后的字符串。若最终为空，输出 $-1$。

样例1

输入

bacdb

输出

b

说明

初始字符串为 $bacdb$，长度 $5$，是奇数。正中间是 $c$，放到下一轮最前面。

从外到内有两对：

• $b$ 与 $b$ 相同，留下 $b$；
• $a$ 与 $d$ 不相邻，留下更靠后的 $d$。

下一轮字符串是 $cbd$。

$cbd$ 长度 $3$，正中间是 $b$。唯一的一对是 $c$ 与 $d$，二者相邻，这一对消失。下一轮只剩中间字符 $b$。

长度为 $1$，停止。输出 $b$。

样例2

输入

bcad

输出

-1

说明

初始字符串为 $bcad$，长度 $4$，是偶数，没有中间字符。

从外到内有两对：

• $b$ 与 $d$ 不相邻，留下 $d$；
• $c$ 与 $a$ 不相邻，留下 $c$。

下一轮字符串是 $dc$。

$d$ 与 $c$ 相邻，这一对消失，下一轮变成空串。长度已经是 $0$，停止。输出 $-1$。