Задача стабильного бракосочетания состоит в установлении отношений между членами двух множеств в соответствии с их предпочтениями. Входные данные состоят из: \begin{itemize} \item множества \textbf{M} из \textbf{n} мужчин; \item множества \textbf{F} из \textbf{n} женщин; \item для каждого мужчины и каждой женщины имеется список членов противоположного пола, заданный в порядке предпочтения (от наиболее предпочтительного до наименее). \end{itemize} Бракосочетанием будем называть однозначное отображение между мужчинами и женщинами. Бракосочетание будем называть стабильным, если не существует такой пары (\textbf{m}, \textbf{f}) что \textbf{f} ∈ \textbf{F} предпочитает \textbf{m} ∈ \textbf{M} своему текущему партнеру, а \textbf{m} предпочитает \textbf{f} своему текущему партнеру. Стабильное бракосочетание \textbf{A} называется оптимальным по отношению к мужчинам, если не существует такого стабильного бракосочетания \textbf{B}, в котором какому-нибудь мужчине соответствует женщина, которую он больше предпочитает, нежели та, которая присвоена ему в \textbf{A}. По заданным спискам предпочтений для каждого мужчины и каждой женщины следует найти стабильное бракосочетание, оптимальное по отношению к мужчинам. \InputFile Первая строка содержит количество тестов. Первая строка каждого теста содержит целое число \textbf{n} (\textbf{0} < \textbf{n} < \textbf{27}). В следующей строке заданы имена \textbf{n} мужчин и \textbf{n} женщин. Мужские имена начинаются прописными буквами, а женские заглавными. Далее идут \textbf{n} строк, которые описывают списки предпочтений для мужчин. Следующие \textbf{n} строк описывают списки предпочтений для женщин. \OutputFile Для каждого теста следует вывести пары стабильного бракосочетания, оптимального по отношению к мужчинам. Пары следует выводить в лексикографическом порядке мужских имен как показано в примере. Между тестами следует выводить пустую строку.