CF1560E.Polycarp and String Transformation

Polycarp has a string $s$. Polycarp performs the following actions until the string $s$ is empty ($t$ is initially an empty string):

• he adds to the right to the string $t$ the string $s$, i.e. he does $t = t + s$, where $t + s$ is a concatenation of the strings $t$ and $s$;
• he selects an arbitrary letter of $s$ and removes from $s$ all its occurrences (the selected letter must occur in the string $s$ at the moment of performing this action).

Polycarp performs this sequence of actions strictly in this order.

Note that after Polycarp finishes the actions, the string $s$ will be empty and the string $t$ will be equal to some value (that is undefined and depends on the order of removing).

E.g. consider $s$="abacaba" so the actions may be performed as follows:

• $t$="abacaba", the letter 'b' is selected, then $s$="aacaa";
• $t$="abacabaaacaa", the letter 'a' is selected, then $s$="c";
• $t$="abacabaaacaac", the letter 'c' is selected, then $s$="" (the empty string).

You need to restore the initial value of the string $s$ using only the final value of $t$ and find the order of removing letters from $s$.

Polycarp 有一个字符串 $s$。Polycarp 执行以下操作，直到字符串 $s$ 为空（初始时 $t$ 为空字符串）：

• 他将字符串 $s$ 添加到字符串 $t$ 的右侧，即执行 $t = t + s$，其中 $t + s$ 表示字符串 $t$ 与 $s$ 的拼接；
• 他任意选择 $s$ 中的一个字母，并从 $s$ 中删除该字母的所有出现（所选字母在执行此操作时必须在字符串 $s$ 中存在）。

Polycarp 严格按上述顺序执行这一系列操作。

注意：当 Polycarp 完成所有操作后，字符串 $s$ 将为空，而字符串 $t$ 将等于某个值（该值未定义，且取决于删除字母的顺序）。

例如，考虑 $s$ = "abacaba"，则操作可能如下进行：

• $t$ = "abacaba"，选择字母 'b'，然后 $s$ = "aacaa"；
• $t$ = "abacabaaacaa"，选择字母 'a'，然后 $s$ = "c"；
• $t$ = "abacabaaacaac"，选择字母 'c'，然后 $s$ = ""（空字符串）。

你需要仅利用最终的 $t$ 值来还原初始字符串 $s$，并找出从 $s$ 中删除字母的顺序。

The first line contains one integer $T$ ($1 \le T \le 10^4$) — the number of test cases. Then $T$ test cases follow.

Each test case contains one string $t$ consisting of lowercase letters of the Latin alphabet. The length of $t$ doesn't exceed $5 \cdot 10^5$. The sum of lengths of all strings $t$ in the test cases doesn't exceed $5 \cdot 10^5$.

第一行包含一个整数 $T$（$1 \le T \le 10^4$）—— 表示测试用例的数量。随后是 $T$ 个测试用例。

每个测试用例包含一个字符串 $t$，该字符串仅由拉丁字母的小写字母组成。字符串 $t$ 的长度不超过 $5 \cdot 10^5$。所有测试用例中字符串 $t$ 的长度总和不超过 $5 \cdot 10^5$。

For each test case output in a separate line:

• $-1$, if the answer doesn't exist;
• two strings separated by spaces. The first one must contain a possible initial value of $s$. The second one must contain a sequence of letters — it's in what order one needs to remove letters from $s$ to make the string $t$. E.g. if the string "bac" is outputted, then, first, all occurrences of the letter 'b' were deleted, then all occurrences of 'a', and then, finally, all occurrences of 'c'. If there are multiple solutions, print any one.

对于每个测试用例，在单独的一行中输出：

• 若答案不存在，输出 $-1$；
• 否则输出两个由空格分隔的字符串。第一个字符串必须为 $s$ 的一个可能的初始值；第二个字符串必须为一个字母序列——表示为了将字符串 $s$ 变为字符串 $t$，需要按该顺序依次删除 $s$ 中的字母。例如，若输出字符串为 "bac"，则表示首先删除所有 'b' 字符，然后删除所有 'a' 字符，最后删除所有 'c' 字符。若存在多个解，输出任意一个即可。

The first test case is considered in the statement.

题目描述中已考虑第一个测试用例。