Pairing

Time limit3sMemory limit128 MB

Summary

Given complete preference rankings of N men and N women, compute the man-optimal stable pairing.

Level: Medium5 of 10
Topics: Greedy, Simulation, Queue
Solved: No attempts yet

Problem

There are $n$ men and $n$ women to pair up. Every man is paired with exactly one woman, and every woman is paired with exactly one man. Each person ranks everyone on the other side from most preferred to least preferred, with no ties.

A pairing is stable when this holds: there is no man $m$ and woman $w$ , not paired with each other, such that $m$ prefers $w$ to his own partner and $w$ prefers $m$ to her own partner.

Several stable pairings can exist, so print only the man-optimal one. In the man-optimal pairing, every man is paired with the woman he prefers most among the women who are his partner in at least one stable pairing. This pairing always exists and it is unique.

Given every ranking, find that pairing.

Input

The first line contains the number of people $N$ ( $1 \le N \le 1000$ ). The men are numbered 1 to $N$ , and the women are numbered 1 to $N$ as well.

Line $i$ of the next $N$ lines holds the ranking of man $i$ . It lists every number from 1 to $N$ once, with the number of the more preferred woman earlier in the line.

Line $j$ of the following $N$ lines holds the ranking of woman $j$ in the same format.

Output

Print $N$ lines. Line $i$ holds the number of the woman paired with man $i$ in the man-optimal pairing.

Examples2

Example 1

Input

Expected output

Example 2
Input
```
2
1 2
2 1
2 1
1 2
```
Expected output
```
1
2
```