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$$$ 中删除字母的顺序。
输入
第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 10^4$$$) — 测试用例的数量。然后是 $$$T$$$ 测试用例。
每个测试用例包含一个由拉丁字母小写字母组成的字符串$$$t$$$。 $$$t$$$ 的长度不超过 $$$5 \cdot 10^5$$$。测试用例中所有字符串 $$$t$$$ 的长度总和不超过 $$$5 \cdot 10^5$$$。
输出
对于单独行中的每个测试用例输出:
- $$$-1$$$,如果答案不存在;
- 用空格分隔的两个字符串。第一个必须包含可能的初始值 $$$s$$$。第二个必须包含一系列字母 - 需要按照什么顺序从 $$$s$$$ 中删除字母才能形成字符串 $$$t$$$。例如。如果输出字符串“bac”,则首先删除所有出现的字母“b”,然后删除所有出现的“a”,最后删除所有出现的“c”。如果有多种解决方案,请打印其中之一。
示例
输入 #1
7 abacabaaacaac nowyouknowthat polycarppoycarppoyarppyarppyrpprppp isi everywherevrywhrvryhrvrhrvhv haaha qweqeewew
输出 #1
abacaba bac -1 polycarp lcoayrp is si everywhere ewyrhv -1 -1
注意
声明中考虑了第一个测试用例。