형곤이의 소개팅

연애가 하고 싶은 형곤이는 소개팅으로 자신의 짝을 만나려고 한다. 형곤이의 소개팅에는 특별한 규칙이 있다.

남자와 여자가 각각 N명씩 만나서 서로가 만나고 싶은 순위를 정하고, 이를 바탕으로 최적의 짝을 만든다. 일반적인 소개팅이라면 성공 확률이 높지 않겠지만 이 소개팅의 성공률은 100%이다. 모든 사람이 서로 만족할 수 있는 최적의 짝을 정해 준다. 최적의 짝이란 임의의 남녀 쌍에 대해 두 사람이 각자 현재 파트너보다 상대를 더 선호하는 경우가 없는 매칭을 말한다. 예를 들어 남자와 여자가 각각 2명일 때 다음 경우를 생각해 보자.

남자와 여자가 각각 2명씩 소개팅에 참여한다. 남자1은 [여자1, 여자2], 남자2는 [여자2, 여자1], 여자1은 [남자1, 남자2], 여자2는 [남자2, 남자1] 순서로 만나고 싶어한다고 하자. 이때 남자1-여자2, 남자2-여자1로 매칭하는 것은 최적의 짝이 아니다. 남자1과 여자1은 현재 자신의 파트너보다 서로를 더 선호하기 때문이다. 형곤이의 소개팅에서 최적의 짝을 찾는 프로그램을 작성해 보자. 최적의 짝이 여러 개라면 아무거나 구해도 된다.

첫 번째 줄에는 남자와 여자의 수를 나타내는 N (1 ≤ N ≤ 200)이 주어진다.

두 번째 줄과 세 번째 줄에는 각각 N명의 남자, N명의 여자의 이름이 주어진다.

이름은 알파벳 소문자와 숫자로 이루어져 있으며 길이는 4글자 이상 10글자 이하이다.

4번째 줄부터 N + 3번째 줄까지는 각각 N+1명의 이름이 주어진다. 첫 번째는 남자의 이름이고, 그 뒤에는 그 남자가 선호하는 순서대로 모든 여자의 이름이 주어진다.

N + 4번째 줄부터 2N + 3번째 줄까지는 각각 N+1명의 이름이 주어진다. 첫 번째는 여자의 이름이고, 그 뒤에는 그 여자가 선호하는 순서대로 모든 남자의 이름이 주어진다.

모든 이름은 유일하며, 성별이 달라도 같은 이름이 존재하지 않는다.

두, 세 번째 줄에 나오는 남자와 여자 이름의 순서는 그 뒤에 나오는 남자와 여자 이름의 순서와 관계가 없다.

N개의 줄에 각각 남자와 여자를 매칭한 결과를 남자 이름과 여자 이름 순으로 공백을 두어 출력한다.

출력하는 순서는 상관없다.