У Поликарп есть строка \(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\).
Выходные данные
Для каждого набора входных данных выведите в отдельной строке:
- \(-1\), если ответа не существует;
- две строки через пробел. Первая строка должна содержать начальное возможное значение \(s\). Вторая строка должна содержать последовательность букв — в каком порядке надо удалять буквы из \(s\), чтобы получилась строка \(t\). Например, если выведена строка «bac», то сначала удалялись все вхождения буквы 'b', потом — все вхождения буквы 'a', затем — все вхождения буквы 'c'. Если существует несколько решений, выведите любое из них.
Примечание
Первый набор входных данных разобран в условии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
abacabaaacaac
nowyouknowthat
polycarppoycarppoyarppyarppyrpprppp
isi
everywherevrywhrvryhrvrhrvhv
haaha
qweqeewew
|
abacaba bac
-1
polycarp lcoayrp
is si
everywhere ewyrhv
-1
-1
|