Polycarp and String Transformation

题意翻译

Polycarp 有一个给定的字符串 $s$ 和初始为空的字符串 $t$。他将会重复以下操作直到字符串 $s$ 为空： - 在 $t$ 后面拼接 $s$，然后选择一个 $s$ 中的字母并删去 $s$ 当中出现的这个字母。 例如，如果 $s=\texttt{abacaba}$，并执行以下操作。 - 在 $t$ 后面拼接 $s$，然后删去 $s$ 当中所有出现的 $\texttt b$。在这次操作之后，$t=\texttt{abacaba}$，$s=\texttt{aacaa}$。 - 在 $t$ 后面拼接 $s$，然后删去 $s$ 当中所有出现的 $\texttt a$。在这次操作之后，$t=\texttt{abacabaaacaa}$，$s=\texttt{c}$。 - 在 $t$ 后面拼接 $s$，然后删去 $s$ 当中所有出现的 $\texttt c$。在这次操作之后，$t=\texttt{abacabaaacaac}$，$s$ 为空字符串。 因此，最终的字符串 $t$ 为 $\texttt{abacabaaacaac}$。 现在给你操作完之后的字符串 $t$。请你回答：是否存在一个字符串 $s$ 和一个删字母的顺序，使得操作完以后可以得到字符串 $t$？如果可以，请你求出 $s$ 和删字母的顺序，否则输出 `-1`。 $T$ 组数据，$1\leqslant T\leqslant 10^4$，$1\leqslant |t|,\sum|t|\leqslant 5\times 10^5$。 Translated by Eason_AC 2021.8.19

题目描述

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 $ .

输入输出格式

输入格式

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 $ .

输出格式

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

7
abacabaaacaac
nowyouknowthat
polycarppoycarppoyarppyarppyrpprppp
isi
everywherevrywhrvryhrvrhrvhv
haaha
qweqeewew

输出样例 #1

abacaba bac
-1
polycarp lcoayrp
is si
everywhere ewyrhv
-1
-1

说明

The first test case is considered in the statement.