Polycarp and String Transformation solution codeforces
Polycarp has a string. Polycarp performs the following actions until the string is empty ( is initially an empty string):
- he adds to the right to the string the string , i.e. he does , where is a concatenation of the strings and ;
- he selects an arbitrary letter of the selected letter must occur in the string ). at the moment of performing this action and removes from all its occurrences (
Polycarp performs this sequence of actions strictly in this order.
Note that after Polycarp finishes the actions, the stringwill be empty and the string will be equal to some value (that is undefined and depends on the order of removing). Polycarp and String Transformation solution codeforces
E.g. consider abacaba” so the actions may be performed as follows:=”
- abacaba“, the letter ‘b‘ is selected, then =”aacaa“; =”
- abacabaaacaa“, the letter ‘a‘ is selected, then =”c“; =”
- abacabaaacaac“, the letter ‘c‘ is selected, then =”” (the empty string). =”
You need to restore the initial value of the stringusing only the final value of and find the order of removing letters from .
The first line contains one integer( ) — the number of test cases. Then test cases follow.
Each test case contains one stringconsisting of lowercase letters of the Latin alphabet. The length of doesn’t exceed . The sum of lengths of all strings in the test cases doesn’t exceed .
For each test case output in a separate line: Polycarp and String Transformation solution codeforces
- , if the answer doesn’t exist;
- two strings separated by spaces. The first one must contain a possible initial value of 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. . The second one must contain a sequence of letters — it’s in what order one needs to remove letters from to make the string . E.g. if the string “
7 abacabaaacaac nowyouknowthat polycarppoycarppoyarppyarppyrpprppp isi everywherevrywhrvryhrvrhrvhv haaha qweqeewew
abacaba bac -1 polycarp lcoayrp is si everywhere ewyrhv -1 -1
The first test case is considered in the statement.