Гра "Заміна"
Минулого року ви винайшли гру, в яку можна грати за допомогою дошки та кубика. Цього року ви створили ще одну гру, яка використовує рядок, що складається з певних літер.
Гра починається з рядка, що містить 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" (без лапок).