У Поликарп есть строка \(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\).