Farmer John có \(N\) món quà được đánh số \(1\ldots N\) dành cho \(N\) con bò cũng được đánh số \(1\ldots N\) (\(1\le N\le 500\)). Mỗi con bò có một danh sách mong muốn là một hoán vị của toàn bộ \(N\) món quà; con bò thích những món xuất hiện sớm hơn trong danh sách hơn những món xuất hiện muộn hơn.

FJ đã lười biếng và chỉ gán quà \(i\) cho bò \(i\) với mọi \(i\). Giờ đây, đàn bò đã tụ họp và quyết định phân phối lại các món quà sao cho sau khi phân phối lại, mỗi con bò nhận được chính món quà ban đầu của mình hoặc một món mà nó thích hơn món ban đầu.

Với mỗi \(i\) từ \(1\) đến \(N\), hãy tìm món quà được yêu thích nhất mà bò \(i\) có thể hy vọng nhận được sau khi phân phối lại.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa danh sách ưu tiên của một con bò. Bảo đảm rằng mỗi dòng là một hoán vị của \(1\dots N\).

Dữ liệu ra

In ra \(N\) dòng; dòng thứ \(i\) chứa món quà được yêu thích nhất mà bò \(i\) có thể hy vọng nhận được sau khi phân phối lại.

Phân nhóm

• Các test 2–3 thỏa mãn \(N\le 8\).
• Các test 4–11 không có ràng buộc bổ sung.

Ví dụ

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4

1
3
2
4

Nguồn

USACO 2022 February Contest, Silver — Redistributing Gifts: https://usaco.org/index.php?page=viewproblem2&cpid=1206

Tác giả: Benjamin Qi.