Игра на обмен
В прошлом году вы изобрели игру с доской и кубиком, а в этом году придумали новую игру, в которую можно играть, используя строку из букв.
Игра начинается с строки из N строчных английских букв (от 'a' до 'z'). В этой строке вы можете менять местами любые два разных символа, и делать это можно сколько угодно раз, включая ноль. Ваша цель — получить лексикографически наименьшую строку после выполнения этих операций.
Однако есть ограничения на конечную строку. Для каждой позиции строки допустимы только определённые буквы (для каждой позиции они могут быть разными). Например, первая буква может быть 'a' или 'b', вторая — 'b' или 'c', и так далее.
Важно отметить, что эти ограничения касаются только конечной строки. Это значит, что в процессе перемещений вы можете временно получить недопустимую строку, если в итоге она станет допустимой после дополнительных перемещений.
Вам дана начальная строка и ограничения для каждой позиции. Ваша задача — написать программу, которая найдёт лексикографически наименьшую допустимую строку после выполнения нуля или более перемещений.
Примечание: При сравнении двух строк одинаковой длины лексикографически меньшей считается та, у которой первая отличающаяся буква меньше.
Входные данные
Ваша программа будет протестирована на одном или нескольких тестах. Первая строка ввода содержит одно целое число T, количество тестов (1 ≤ T ≤ 100). Далее следуют тесты. Каждый тест начинается с строки, содержащей начальную строку S, состоящую из N строчных английских букв (1 ≤ N ≤ 100). Затем следуют N строк, каждая из которых содержит строку C_{i }, состоящую из L_i различных строчных английских букв (1 ≤ L_i ≤ 5), которые являются допустимыми для i-й позиции в конечной строке. Каждая буква в каждом C_i встречается хотя бы один раз в S.
Выходные данные
Для каждого теста выведите в одной строке лексикографически наименьшую допустимую строку, которую можно получить после выполнения нуля или более перемещений. Если такой допустимой строки нет, выведите "NO SOLUTION" (без кавычек).