Description
There are N SAs and N students. Each SA has to help a student one-to-one. However, each SA has a rank of preference for different students, and each student has a rank of preference for different SAs.
Hong has to make a stable matching table that one SA matches one student. Assume that in a matching table, SA A matches student a , SA B matches student b . If A prefer b to a , and b prefer A to B , the matching table is not stable.
It's very difficult for Hong to solve the problem. So she asks you to help her. Write a program to make a stable matching table. Give priority to SAs.
Input
The first line contains one integer N which shows the number of SAs. The number of students is N , too.
The next line contains N strings separated by one space. The i-th string shows the name of the i-th SA.
The next line contains N strings z. The i-th string shows the name of the i-th student.
Each of the next N lines contains N strings S1...SN separated by one space. S1...SN is a permutation of students' names. The i-th line shows the preference order of the i-th SA. The SA prefers Si to S{i+1}..SN.
Each of the next N lines contains N strings S1...SN separated by one space. S1...SN is a permutation of SAs' names. The i-th line shows the preference order of the i-th student. The student prefers Si to S{i+1}..SN.
The length of each string ≤ 10.
Output
Output a line contains N strings. The i-th string S_iS**i means that the i-th SA matches student S_iS**i.
Sample Input 1
3
adam bale campbell
alice bob calvin
bob calvin alice
calvin bob alice
bob alice calvin
adam bale campbell
adam campbell bale
bale adam campbell
Sample output 1
bob calvin alice
Sample Input 2
5
adam bale campbell daisy eddy
alice bob calvin david emily
david calvin alice emily bob
bob alice calvin david emily
alice emily david calvin bob
alice calvin david bob emily
alice bob calvin david emily
campbell bale adam daisy eddy
eddy daisy bale adam campbell
daisy bale adam campbell eddy
campbell daisy adam eddy bale
bale adam eddy campbell daisy
Sample Output 2
david emily alice calvin bob
Limit
1 second for each test case. The memory limit is 256MB. For 100% test cases, N \leq≤ 1000.
