У Фермера Джона є \(N\) подарунків помічених числами \(1\ldots N\) для його \(N\) корів, також помічених числами \(1\ldots N\) (\(1\le N\le 500\)). Кожна корова має список переваг, який є перестановкою з усіх \(N\) подарунків, так що корова віддає перевагу подарунку, який з'явився у списку раніше за подарунок, який з'явився у списку пізніше.

ФД чепрез лінощі просто призначив корові \(i\) подарунок \(i\) для всіх \(i\). Тепер корови зібралися та вирішили перепризначити подарунки так, щоб у кожної корови або залишився початковий подарунок, або він був замінений на більш улюблений подарунок.

Для кожного \(i\) від \(1\) до \(N\), виведіть найбільш вподобаний подарунок який може отримати корова після перепризначення.

Формат вхідних даних

Перший рядок містить \(N\). Наступні \(N\) рядків містять перелік переваги корови.

Гарантується, що кожен рядок формує перестановку чисел \(1\dots N\).

Формат вихідних даних

Виведіть \(N\) рядків, \(i\)-ий з яких містить найбільш бажаний подарунок, який може отримати корова \(i\) після перепризначення.

Приклад вхідних даних

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

Приклад вихідних даних

1
3
2
4

У цьому прикладі можливі два перепризначення:

Оригінальне призначення:

• корова \(1\) отримала подарунок \(1\),
• корова \(2\) отримала подарунок \(2\),
• корова \(3\) отримала подарунок \(3\),
• корова \(4\) отримала подарунок \(4\).

• Корова \(1\) отримала подарунок \(1\),
• корова \(2\) отримала подарунок \(3\),
• корова \(3\) отримала подарунок \(2\),
• корова \(4\) отримала подарунок \(4\).

Зауважимо, що корови \(1\) і \(4\) не можуть отримати подарунок краще ніж оригінальний. А корови \(2\) і \(3\) можуть.

ОЦІНЮВАННЯ:

• У тестах 2-3 \(N\le 8\).
• У тестах 4-11 немає додаткових обмежень.

Автор: Benjamin Qi