E. Поликарп и преобразование строки
ограничение по времени на тест
3 с
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарп есть строка $$$s$$$. Поликарп делает следующие действия до тех пор, пока строка $$$s$$$ не станет пустой (изначально $$$t$$$ — пустая строка):

  • дописывает справа к $$$t$$$ строку $$$s$$$, то есть совершает присвоение $$$t = t + s$$$, где $$$t + s$$$ обозначает конкатенацию (соединение) строк $$$t$$$ и $$$s$$$;
  • выбирает произвольным образом какую-то одну букву из $$$s$$$ и удаляет из $$$s$$$ все её вхождения (выбранная буква обязательно должна встречаться в $$$s$$$ на момент выполнения этого действия).

Поликарп выполняет данную последовательность действий строго в заданном порядке.

Отметим, что в конце концов строка $$$s$$$ станет пустой, а строка $$$t$$$ будет равна некоторому значению (и это значение определяется неоднозначно, оно зависит от порядка удаления).

Например, если изначально $$$s$$$=«abacaba», то события могли разворачиваться следующим образом:

  • $$$t$$$=«abacaba», выбрана буква 'b', теперь $$$s$$$=«aacaa»;
  • $$$t$$$=«abacabaaacaa», выбрана буква 'a', теперь $$$s$$$=«c»;
  • $$$t$$$=«abacabaaacaac», выбрана буква 'c', теперь $$$s$$$=«» (пустая строка).

Вам необходимо восстановить исходное значение строки $$$s$$$ по итоговому значению $$$t$$$ и найти порядок, в котором удалялись буквы из $$$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'. Если существует несколько решений, выведите любое из них.
Пример
Входные данные
7
abacabaaacaac
nowyouknowthat
polycarppoycarppoyarppyarppyrpprppp
isi
everywherevrywhrvryhrvrhrvhv
haaha
qweqeewew
Выходные данные
abacaba bac
-1
polycarp lcoayrp
is si
everywhere ewyrhv
-1
-1
Примечание

Первый набор входных данных разобран в условии.