육감

Ms. Future는 예지 능력을 지녔다. 자신의 행동만 빼고 모든 참가자의 행동을 정확히 예견할 수 있으므로, 당연히 몇몇 카드 게임에서 뛰어난 실력을 보인다. 오늘 그녀는 무모한 도박꾼 Mr. Past의 도전을 받아들였다. 두 사람은 간단한 2인 trick-taking 카드 게임을 하기로 했다.

게임에 쓰는 카드는 한쪽 면에 숫자가 인쇄되어 있고 다른 쪽은 비어 있어 다른 카드와 구별되지 않는다.

게임은 두 참가자에게 같은 수, 이를테면 n장의 카드를 나눠 주면서 시작하고, 인쇄된 숫자는 상대에게 보이지 않는다.

게임은 n번의 트릭으로 이루어진다. 각 트릭에서 두 참가자는 자신의 손에서 카드 한 장을 낸다. 더 큰 숫자의 카드를 낸 참가자가 그 트릭을 가져간다. Ms. Future가 이 게임에 매우 능숙하므로, 두 사람이 같은 숫자의 카드를 냈을 때는 Mr. Past에게 트릭을 주기로 합의했다. 한 번 사용한 카드는 같은 게임에서 다시 사용할 수 없다. 게임은 손에 든 카드를 모두 쓸 때까지 계속된다. 게임의 목표는 최대한 많은 트릭을 가져가는 것이다.

이 문제에서 여러분의 임무는 Ms. Future가 손에 든 카드를 낼 최선의 순서를 정하는 컴퓨터 프로그램을 작성해서 그녀를 돕는 것이다. 그녀에게는 육감이 있으므로, 여러분의 프로그램은 게임 전에는 보통 사람이 쓸 수 없는 정보를 활용할 수 있다.

입력은 다음과 같은 형식의 테스트 케이스 하나로 이루어진다.

n
p1 · · · pn
f1 · · · fn

첫 줄의 n은 트릭의 수이며 2 이상 5000 이하의 정수이다. 둘째 줄은 Mr. Past가 손에 든 카드를 내는 순서를 나타낸다. i번째 트릭에서 그는 숫자 pi인 카드를 낸다 (1 ≤ i ≤ n). 셋째 줄은 Ms. Future의 손을 나타낸다. fi (1 ≤ i ≤ n)는 그녀가 딜러에게서 i번째로 받은 카드에서 볼 숫자이다. 둘째 줄과 셋째 줄의 모든 숫자는 1 이상 10 000 이하의 정수이다. 이 줄에는 같은 숫자가 여러 번 나올 수 있다.

출력은 공백으로 구분된 n개의 정수 a1 · · · an을 한 줄에 담아야 한다. 여기서 ai (1 ≤ i ≤ n)는 가져가는 트릭의 수를 최대로 만들기 위해 i번째 트릭에서 그녀가 내야 하는 카드의 숫자이다. 그러한 숫자열이 둘 이상이면 그중 사전순으로 가장 큰 것을 출력한다.