The stable marriage problem consists of matching members of two different sets according to the member’s preferences for the other set’s members. The input for our problem consists of: \begin{itemize} \item a set \textbf{M} of \textbf{n} males; \item a set \textbf{F} of \textbf{n} females; \item for each male and female we have a list of all the members of the opposite gender in order of preference (from the most preferable to the least). \end{itemize} A marriage is a one-to-one mapping between males and females. A marriage is called stable, if there is no pair (\textbf{m}, \textbf{f}) such that \textbf{f} ∈ \textbf{F} prefers \textbf{m} ∈ \textbf{M} to her current partner and \textbf{m} prefers \textbf{f} over his current partner. The stable marriage \textbf{A} is called male-optimal if there is no other stable marriage \textbf{B}, where any male matches a female he prefers more than the one assigned in \textbf{A}. Given preferable lists of males and females, you must find the male-optimal stable marriage. \InputFile The first line gives you the number of tests. The first line of each test case contains integer \textbf{n} (\textbf{0} < \textbf{n} < \textbf{27}). Next line describes \textbf{n} male and \textbf{n} female names. Male name is a lowercase letter, female name is an upper-case letter. Then go \textbf{n} lines, that describe preferable lists for males. Next \textbf{n} lines describe preferable lists for females. \OutputFile For each test case find and print the pairs of the stable marriage, which is male-optimal. The pairs in each test case must be printed in lexicographical order of their male names as shown in sample output. Output an empty line between test cases.