Усі політики невідомої, повністю вигаданої і абсолютно нереалістичної країни проводять свій час, звинувачуючи один одного на національному телебаченні замість того, щоб виконувати свою роботу. Все почалося одного недільного дня, коли політик номер 1 був гостем у першому епізоді (нині дуже популярного) ток-шоу. Під час шоу він звинуватив політика номер 2 у поганому стані країни. Природно, у другому епізоді шоу гостем був політик номер 2. Ведучий ток-шоу повідомив своєму гостю, що політик номер 1 звинуватив його, і політик номер 2 потім звинуватив іншого політика. Новозвинувачений політик був гостем у наступному шоу, де ведучий повідомив йому, що...

Навіть сьогодні, після майже 20 років, новий політик є гостем у кожному епізоді шоу, де йому повідомляють, хто звинуватив його у поганому стані країни. Цей політик потім звинувачує іншого політика, і порочне коло продовжується. Щоб зробити все цікавішим, ми ексклюзивно дізналися, що кожен політик має фіксовану стратегію поведінки під час шоу. Точніше, кожен політик знає, кого звинуватити, базуючись на тому, хто звинуватив його у попередньому шоу. Ми надамо вам цю інформацію і сподіваємося, що ви зможете написати програму, яка обчислює, який політик буде гостем ~K~-го шоу.

Input

Перший рядок містить цілі числа ~N(2 \leq N \leq 500)~ та ~K(1 \leq K \leq 10^{18})~ з опису задачі.

~i~-й з наступних ~N~ рядків містить ~N~ цілих чисел, де ~j~-те число вказує нам, кого звинуватить ~i~-й політик, якщо його звинуватив політик номер ~j~ в останньому шоу.

Можна припустити, що жоден політик ніколи не звинуватить себе. Тому жодне з чисел у ~i~-му рядку матриці не буде дорівнювати ~i~. Аналогічно, зауважте, що ~i~-те число в ~i~-му рядку матриці завжди буде дорівнювати 0 і може бути проігнороване.

Output

В одному рядку ви повинні вивести номер політика, який буде гостем ~K~-го епізоду ток-шоу.

Оцінювання

У тестових випадках загальною вартістю 49 балів буде виконуватися умова ~1 \leq K \leq 10^{5}~.

Sample Input 1

2 4
0 2
1 0

Sample Output 1

2

Sample Input 2

3 7
0 3 2
3 0 3
2 1 0

Sample Output 2

1

Sample Input 3

4 7
0 4 3 2
4 0 4 1
2 1 0 1
3 2 3 0

Sample Output 3

3