Вам даны строки \(S\) и \(T\), состоящие из строчных символов латинского алфавита. Гарантируется, что \(T\) является перестановкой строки abc.
Найдите строку \(S'\), которая является лексикографически минимальной перестановкой \(S\), и при этом \(T\) не является подпоследовательностью \(S'\).
Строка \(a\) является перестановкой строки \(b\), если количество вхождений для всех различных символов одинаковое в обеих строках.
Строка \(a\) является подпоследовательностью строки \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно нуля или всех) символов.
Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Выходные данные
Для каждого набора входных данных выведите единственную строку \(S'\), которая является лексикографически минимальной перестановкой \(S\), и при этом \(T\) не является подпоследовательностью \(S'\).
Примечание
В первом наборе входных данных и aaaabbc, и aaaabcb лексикографически меньше, чем aaaacbb, но они содержат abc как подпоследовательность.
Во втором наборе входных данных abccc является лексикографически минимальной перестановкой cccba и не содержит acb как подпоследовательность.
В третьем наборе входных данных bcdis является лексикографически минимальной перестановкой dbsic и не содержит bac как подпоследовательность.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
abacaba
abc
cccba
acb
dbsic
bac
abracadabra
abc
dddddddddddd
cba
bbc
abc
ac
abc
|
aaaacbb
abccc
bcdis
aaaaacbbdrr
dddddddddddd
bbc
ac
|