В далеком созвездии Тау Кита все стало для нас непонятно. В частности, таукитяне очень хитро выбирают имена своим детям.
Молодые родители abac и bbad думают как назвать своего первенца. Решено, что имя будет перестановкой букв строки s. Чтобы не отставать от соседей, они решили назвать ребеночка так, чтобы имя оказалось лексикографически строго больше имени t соседского сына.
С другой стороны, они подозревают о скором введении налога на имена. В соответствии с ним таукитяне с лексикографически большими именами будут платить большие суммы. По этой причине abac и bbad хотят назвать первенца так, чтобы имя было лексикографически строго больше имени t и при этом лексикографически наименьшим.
Лексикографический порядок строк — это привычный нам порядок «как в словаре». Такое сравнение используется во всех современных языках программирования для сравнения строк. Формально, строка p длины n лексикографически меньше строки q длины m, если верно одно из двух утверждений:
- n < m, а p является началом (префиксом) строки q (например, «aba» меньше строки «abaa»),
- p1 = q1, p2 = q2, ..., pk - 1 = qk - 1, pk < qk для некоторого k (1 ≤ k ≤ min(n, m)), здесь символы в строках нумеруются от 1.
Напишите программу, которая по заданной строке s и имени соседского ребенка t определяет такую строку, которая получается перестановкой букв s, лексикографически строго больше t и при этом лексикографически как можно меньше.
Примечание
В первом примере данная строка s является искомой, следовательно, порядок букв в ней менять не надо.