Gzh之软院联谊

题目描述

软院男女比8:1，耿导因为担心大家的感情问题，甚是苦恼。于是，耿导找来了Gzh，让他和中华女子学院（耿导钦点的，谈起他们和女院联谊的时候还一脸怀念）联谊。

假设软院和中华女子学院各有n个班级，他们之间各有一个满意优先度，如果1和2联谊了，3和4联谊了（1,3是软院班级，2,4是女院班级），但1比起2更满意4,同时4比起3更满意1，这时联谊就会破裂，现在给出每个班级的满意优先度，请你求出一份不会破裂的联谊配对（以更令软院班级满意的结果优先考虑）。

输入

第一个数为数据组数m接下来m组，每组第一行为班级数n。接下来一行为2*n个字符，分别表示软院班级和女院班级，软院班级为一个小写字母，女院班级为一个大写字母。接下来为2*n行，每行表示一个班级的满意优先度（先给出软院，后给出女院）。

输出

对于每组数据，输出n行，为最终的联谊配对，以软院班级名字升序排列，每组数据之间有一个空行。

输入样例

1
2
a b A B
a:AB
b:AB
A:ab
B:ab

输出样例

a A
b B