CF1560E Polycarp and String Transformation

Polycarp 有一个字符串 $s$。Polycarp 按照以下步骤不断操作，直到字符串 $s$ 变为空（$t$ 初始为空字符串）： - 他将字符串 $s$ 添加到 $t$ 的右侧，即执行 $t = t + s$，其中 $t + s$ 表示字符串 $t$ 和 $s$ 的拼接； - 他从 $s$ 中任选一个字母，并将 $s$ 中所有该字母的出现全部删除（所选字母必须在当前 $s$ 中出现）。 Polycarp 必须严格按照上述顺序执行操作。 注意，操作结束后，字符串 $s$ 会变为空，字符串 $t$ 会变成某个值（该值不唯一，取决于删除字母的顺序）。 例如，考虑 $s$ = "abacaba"，操作过程可能如下： - $t$ = "abacaba"，选择字母 'b'，此时 $s$ = "aacaa"； - $t$ = "abacabaaacaa"，选择字母 'a'，此时 $s$ = "c"； - $t$ = "abacabaaacaac"，选择字母 'c'，此时 $s$ = ""（空串）。 现在，给定最终的字符串 $t$，你需要还原初始的字符串 $s$，并找出删除字母的顺序。

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。接下来有 $T$ 个测试用例。 每个测试用例包含一行字符串 $t$，仅由小写拉丁字母组成。$t$ 的长度不超过 $5 \cdot 10^5$。所有测试用例中 $t$ 的总长度不超过 $5 \cdot 10^5$。

对于每个测试用例，输出一行： - 如果不存在答案，输出 $-1$； - 否则输出两个字符串，用空格分隔。第一个字符串为可能的初始字符串 $s$，第二个字符串为删除字母的顺序。例如，若输出 "bac"，表示先删除所有 'b'，再删除所有 'a'，最后删除所有 'c'。如果有多种解法，输出任意一种即可。

第一个测试用例已在题目描述中给出。 由 ChatGPT 4.1 翻译