AT_oupc2023_day1_d Han Burger

用 $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 翻译