БінКойн

У компанії BinCoin працює $n$ співробітників, пронумерованих від $1$ до $n$. Структура підпорядкування в цій компанії є кореневим деревом. Іншими словами:

• В компанії є один генеральний директор — головний керівник.

• Кожен інший співробітник має рівно одного безпосереднього начальника.

• В структурі підпорядкування немає циклів.

Крім того, через незрозуміле захоплення генерального директора BinCoin усім бінарним, структура підпорядкування в компанії є бінарним кореневим деревом. Це означає, що кожен співробітник є безпосереднім начальником рівно нуля або двох інших співробітників.

На думку генерального директора, робота в цій компанії майже така ж небезпечна, як у шахтах. Таким чином, співробітники час від часу повинні підписувати заяву про відмову від претензій. Цей процес відбувається таким чином. Спочатку генеральний директор бере журнал, а потім рекурсивно виконується наступна процедура:

Якщо співробітник, який має журнал, не має жодних підлеглих, вони підписують заяву в журналі і повертають його своєму безпосередньому начальнику. Процедура завершується, якщо це був генеральний директор, який не має безпосереднього начальника.

Інакше

• вони випадковим чином обирають одного з двох своїх безпосередніх підлеглих та передають журнал одному з них;

• коли вони отримують журнал назад, вони підписують його;

• а потім вони передають його іншому безпосередньому підлеглому;

• коли вони знову отримують його, вони повертають його своєму безпосередньому начальнику. Процедура завершується, якщо це був генеральний директор, який не має безпосереднього начальника.

Усі випадкові вибори є незалежними.

Одного разу генеральний директор зрозумів, що він не може пригадати дерево підпорядкування. На щастя, у нього є журнал з $k$ записами. Кожен запис — це послідовність співробітників у порядку їх підписання в журналі.

Допоможіть генеральному директору відновити дерево підпорядкування.

Вхідні дані

У першому рядку містяться два цілих числа $n$ та $k$ $(1\le n\le 999,50\le k\le 100)$ — кількість співробітників та кількість записів у журналі.

Кожен з наступних $k$ рядків містить перестановку цілих чисел від $1$ до $n$ — порядок співробітників у відповідному записі.

Гарантується, що введення отримане, як описано в умові, із реальним випадковим вибором.

Вихідні дані

Виведіть $n$ цілих чисел $p_i$. Якщо $i$ є генеральним директором, то $p_i$ має бути $-1$. В іншому випадку $p_i$ повинно бути індексом безпосереднього начальника $i$-го співробітника.

Ваш вивід повинен відповідати бінарному кореневому дереву. Якщо існує кілька дерев, які задовольняють введенню, ви можете вивести будь-яке з них.

Приклади