시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 56 10 8 18.182%

문제

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

남자와 여자가 각각 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글자 이하이다.

3번째 줄부터 N + 2번째 줄까지는 남자의 이름과 해당 남자의 여자에 대한 선호도가 높은 순서대로 주어진다.

N + 3번째 줄부터 2N + 2번째 줄까지는 여자의 이름과 해당 여자의 남자에 대한 선호도가 높은 순서대로 주어진다

모든 이름은 유일하며 서로 다른 성별 간에도 같은 이름이 존재하지 않는다.

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

출력

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

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

예제 입력 1

3
hyeyoo doby yepark
sunhpark soohchoi yomoon
hyeyoo soohchoi sunhpark yomoon
doby yomoon soohchoi sunhpark
yepark sunhpark soohchoi yomoon
sunhpark yepark hyeyoo doby
soohchoi doby hyeyoo yepark
yomoon hyeyoo doby yepark

예제 출력 1

doby yomoon
hyeyoo soohchoi
yepark sunhpark