B. Azamon Web Services
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для привлечения клиентов на свой сайт Azamon ваш друг Jeff Zebos запустил новую онлайн-кампанию. Однако он не смог привлечь так много посетителей, как планировал. Вам кажется, что самая большая проблема заключается в том, что его сайт не получает высокие места в выдаче поисковых систем. Только если он изменит названия продуктов на такие, которые будут лучше чем у конкурентов, он сможет оказаться на первой строчке в поиске и станет миллионером!

После некоторого исследования, вы заметили, что в поиске результаты отсортированы лексикографически. Если ваш друг сможет переименовать свои продукты на лексикографически меньшие строки, чем у конкурентов, он будет первым в поиске!

Чтобы сделать стратегию менее очевидной для конкурентов, вы решили поменять местами не больше одной пары символов в названиях продуктов.

Пожалуйста, помогите другу улучшить названия своих продуктов, так чтобы они стали лексикографически меньше названия продуктов его конкурентов.

Вам дана строка $$$s$$$, являющаяся названием продукта компании Azamon и строка $$$c$$$, являющаяся названием продукта компании конкурента. Найдите некоторый способ поменять не больше одной пары символов в строке $$$s$$$ (это означает выбрать два различных индекса $$$i$$$ и $$$j$$$ и поменять местами символы $$$s_i$$$ и $$$s_j$$$ в строке), так чтобы новое имя стало лексикографически меньше, чем $$$c$$$. Если это невозможно, определите это.

Примечание: Строка $$$a$$$ лексикографически меньше чем строка $$$b$$$, тогда и только тогда, когда одно из следующих двух условий выполнено:

  • $$$a$$$ это собственный префикс строки $$$b$$$, то есть, $$$a$$$ это префикс строки $$$b$$$ и $$$a \neq b$$$;
  • Существует целое $$$1 \le i \le \min{(|a|, |b|)}$$$, такое что $$$a_i < b_i$$$ и $$$a_j = b_j$$$ для всех $$$1 \le j < i$$$.
Входные данные

В первой строке записано единственное целое число $$$t$$$ ($$$1 \le t \le 1500$$$), количество наборов входных данных. В следующих строках находятся их описания.

Каждый набор входных данных содержит две строки $$$s$$$ и $$$c$$$, разделенные пробелом ($$$2 \le |s| \le 5000, 1 \le |c| \le 5000$$$). Строки $$$s$$$ и $$$c$$$ состоят из прописных букв латинского алфавита.

Гарантируется, что сумма $$$|s|$$$ по всем тестовым случаям не превосходит $$$5000$$$ и что сумма $$$|c|$$$ по всем тестовым случаям не превосходит $$$5000$$$.

Выходные данные

Для каждого набора входных данных выведите строку, содержащую ответ. Ответом на набор входных данных является:

  • новое имя, которое может быть получено из старого обменом не более одной пары символов, которое будет лексикографически меньше, чем $$$c$$$. В случае, если существует несколько возможных ответов, вы можете вывести любой из них;
  • три знака минус (строка «---» без кавычек) если новое имя, удовлетворяющее условию, получить невозможно.
Пример
Входные данные
3
AZAMON APPLE
AZAMON AAAAAAAAAAALIBABA
APPLE BANANA
Выходные данные
AMAZON
---
APPLE
Примечание

В первом наборе входных данных можно поменять второй и четвертый символы строки и получится строка «AMAZON», которая лексикографически меньше чем «APPLE».

Во втором наборе входных данных невозможно улучшить имя продукта так, чтобы удовлетворить все условия.

В третьем наборе входных данных, можно не делать замены пары символов. Это верно, потому что имя «APPLE» лексикографически меньше, чем имя «BANANA». Заметьте, что возможны и другие ответы, например «APPEL».