用 $N$ 个字符或字符串 $X_1, X_2, \dots, X_N$ 按顺序连接得到的字符串，记作 $X_1 + X_2 + \cdots + X_N$。

对于字符串，有如下“吧嘎”、“全吧嘎”和“半吧嘎”的定义。该定义与 E 问题中的相同。

• “吧嘎”指的是全吧嘎的字符串，以及半吧嘎的字符串。
• “全吧嘎”指存在某个吧嘎 $A$ 和某个字符 $c$，使得该字符串可以写成 $c + A + c$ 的形式，同时空字符串也是全吧嘎。
• “半吧嘎”指存在某两个非空吧嘎 $A$ 和 $B$，使得该字符串可以写成 $A + B$，且不是全吧嘎。

例如，abba 和 abbcca 是全吧嘎，aabb 和 abbacc 是半吧嘎，但 abbcbbc 和 ababa 不是吧嘎。

给定一个由小写英文字母组成的字符串 $S$，请找出满足 $S + T$ 为全吧嘎的字符串 $T$，使得 $|T|$ 最小，并在所有满足条件的 $T$（长度最小者中）中字典序最小的一个输出。如果不存在这样的 $T$，输出 -1。

字典序的定义如下：依次比较两个字符串 $S = S_1S_2\cdots S_{|S|}$ 和 $T = T_1T_2\cdots T_{|T|}$，满足下述两个条件之一时，称 $S$ 的字典序小于 $T$。

1. $|S| < |T|$ 且 $S = S_1S_2\cdots S_{|S|} = T_1T_2 \cdots T_{|S|}$。
2. 存在 $1 \leq i \leq \min\{|S|, |T|\}$，同时满足：
   • $S_1S_2\cdots S_{i-1} = T_1T_2\cdots T_{i-1}$
   • $S_i$ 是按字母表顺序小于 $T_i$ 的字符。

输入为一行，包括一个字符串 $S$。

请输出满足题意的 $T$，如无答案输出 -1。

小子任务

1. （1 分）$S$ 只包含 a 和 b，$|S| \leq 10$
2. （99 分）无额外限制

样例解释 1

设 $T = $ aba，则 $S+T = $ abccaaba 是全吧嘎。
当然，满足条件的 $T$ 不止 aba，但长度为 2 或更短的 $T$ 并不存在，而所有长度为 3 的 $T$ 中，字典序最小的是 aba，因此输出 aba。

本测试用例不满足小子任务 1 的限制。

样例解释 2

选择 $T$ 为空字符串则 $S+T = $ abba 是全吧嘎。

本测试用例满足小子任务 1 的限制。

数据范围

• $1 \leq |S| \leq 200{,}000$
• $S$ 是仅含小写英文字母的字符串。

由 ChatGPT 5 翻译