Polycarp and String Transformation
Contest: Codeforces Round 739 (Div. 3)
Difficulty rating: 1800
Tags: binary search, implementation, sortings, strings

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

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The first test case is considered in the statement.

Example input:
7
abacabaaacaac
nowyouknowthat
polycarppoycarppoyarppyarppyrpprppp
isi
everywherevrywhrvryhrvrhrvhv
haaha
qweqeewew

Example output:
abacaba bac
-1
polycarp lcoayrp
is si
everywhere ewyrhv
-1
-1

Editorial:
Suppose it's given a string $$$t$$$ for which the answer exists. Consider the last non-empty value of $$$s$$$. Only $$$1$$$ letter occurs in the value and the letter is the last removed letter. At the same time, the value of $$$s$$$ is a suffix of $$$t$$$ so the last character of $$$t$$$ is the last removed letter. Consider the second-last non-empty value of $$$s$$$. It contains exactly $$$2$$$ distinct letters so that one of them is the last removed letter and the other is the second-last removed letter. The concatenation of the second-last and the last values of $$$s$$$ is a suffix of $$$t$$$ consisting only of the letters. Therefore, the letter which occurrence is the last of the occurrences of all letters except the last removed one is the second-last removed letter. Considering so other values, we are proving that the order of removing the letters is the order the last occurrences of the letters occur in the string $$$t$$$.
Suppose $$$k$$$ is the number of the step in which some letter was removed, $$$c_k$$$ is the number of occurrences of the letter in the initial value of $$$s$$$. The letter occurs in exactly $$$k$$$ different values of $$$s$$$. In each of them, the letter occurs exactly $$$c_k$$$ times. So the letter occurs in $$$t$$$ exactly $$$d_k = k \cdot c_k$$$ times. Therefore, using the number of the step ($$$k$$$) in which the letter was removed and the number of the letter's occurrences in $$$t$$$ ($$$d_k$$$), let's calculate the number of the letter's occurrences in the string $$$s$$$: $$$c_k = \frac{d_k}{k}$$$. If $$$d_k$$$ isn't completely divisible by $$$k$$$, there's no solution.
The sum of all $$$c_k$$$ of all letters occurring in $$$t$$$ is the length of the initial value of $$$s$$$. Since the initial value is a prefix of $$$t$$$, the possible answer is the prefix of $$$t$$$ having the length equal to the sum of all $$$c_k$$$.
Before outputting the prefix, check that you can get from the supposed value of the string $$$s$$$ the string $$$t$$$. Checking it, you may use the algorithm from the statement. If the resulting string is equal to $$$t$$$, the answer is correct and must be outputted, otherwise, there's no solution.