Cow Gift Reassignment

Farmer John has N gifts labeled \(1\cdots N\) for his N cows, also labeled \(1\cdots N\) (\(1\le N\le 500\)). Initially, cow \(i\) is given gift \(i\) for all \(i\). Each cow has a wishlist, which is a permutation of all \(N\) gifts. In the wishlist, a cow prefers gifts that appear earlier over those that appear later.

The cows decide to reassign the gifts amongst themselves so that each cow ends up with either the same gift as originally assigned or a gift she prefers (i.e. one that appears before her originally assigned gift in her wishlist). For each cow \(i\), determine the most preferred gift (the one that appears earliest in her wishlist) that she could possibly obtain in some valid reassignment.

Formally, let cow \(i\)'s allowed set be the gifts that appear in her wishlist at positions \(1\) to \(r_i\), where \(r_i\) is the position of gift \(i\) in her wishlist. We require a permutation \(f\) of \(\{1,2,\dots,N\}\) such that for every cow \(i\), \(f(i)\) is in her allowed set, and for a fixed cow \(j\) we force \(f(j)=g\) for some candidate gift \(g\) in her allowed set. The problem is to choose, for each cow, the most preferred candidate gift for which such a global assignment exists.

inputFormat

The first line contains an integer \(N\) (\(1\le N\le 500\)). Each of the next \(N\) lines contains a permutation of \(1,2,\dots,N\), representing the wishlist of a cow. The \(i\)th line gives the wishlist for cow \(i\). Each wishlist is a space‐separated list of \(N\) integers.

outputFormat

Output a single line with \(N\) space-separated integers. The \(i\)th number should be the most preferred gift cow \(i\) could hope to receive in some valid reassignment.

sample

3
1 2 3
2 3 1
3 1 2

1 2 3