Starting from:
$30

$24

Lab #1: Stable Match Solution




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.

More products