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

• множества M из n мужчин;
• множества F из n женщин;
• для каждого мужчины и каждой женщины имеется список членов противоположного пола, заданный в порядке предпочтения (от наиболее предпочтительного до наименее).

   Бракосочетанием будем называть однозначное отображение между мужчинами и женщинами. Бракосочетание будем называть стабильным, если не существует такой пары (m, f) что f ∈ F предпочитает m ∈ M своему текущему партнеру, а m предпочитает f своему текущему партнеру. Стабильное бракосочетание A называется оптимальным по отношению к мужчинам, если не существует такого стабильного бракосочетания B, в котором какому-нибудь мужчине соответствует женщина, которую он больше предпочитает, нежели та, которая присвоена ему в A.

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

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

   Первая строка содержит количество тестов. Первая строка каждого теста содержит целое число n (0 < n < 27). В следующей строке заданы имена n мужчин и n женщин. Мужские имена начинаются прописными буквами, а женские заглавными. Далее идут n строк, которые описывают списки предпочтений для мужчин. Следующие n строк описывают списки предпочтений для женщин.

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

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