24617번 - Redistributing Gifts 다국어

문제

Farmer John has $N$ gifts labeled 1ドル\ldots N$ for his $N$ cows, also labeled 1ドル\ldots N$ (1ドル\le N\le 500$). Each cow has a wishlist, which is a permutation of all $N$ gifts such that the cow prefers gifts that appear earlier in the list over gifts that appear later in the list.

FJ was lazy and just assigned gift $i$ to cow $i$ for all $i$. Now, the cows have gathered amongst themselves and decided to reassign the gifts such that after reassignment, every cow ends up with the same gift as she did originally, or a gift that she prefers over the one she was originally assigned.

For each $i$ from 1ドル$ to $N,ドル compute the most preferred gift cow $i$ could hope to receive after reassignment.

입력

The first line contains $N$. The next $N$ lines each contain the preference list of a cow. It is guaranteed that each line forms a permutation of 1ドル\dots N$.

출력

Please output $N$ lines, the $i$-th of which contains the most preferred gift cow $i$ could hope to receive after reassignment.

제한

힌트

In this example, there are two possible reassignments:

• The original assignment: cow 1ドル$ receives gift 1ドル,ドル cow 2ドル$ receives gift 2ドル,ドル cow 3ドル$ receives gift 3ドル,ドル and cow 4ドル$ receives gift 4ドル$.
• Cow 1ドル$ receives gift 1ドル,ドル cow 2ドル$ receives gift 3ドル,ドル cow 3ドル$ receives gift 2ドル,ドル and cow 4ドル$ receives gift 4ドル$.

Observe that both cows 1ドル$ and 4ドル$ cannot hope to receive better gifts than they were originally assigned. However, both cows 2ドル$ and 3ドル$ can.