All politicians of an unknown, completely invented and totally unrealistic country are spending their time accusing each other on national television instead of doing their jobs. It all started one Sunday afternoon when politician number 1 was a guest in the first episode of a (now very popular) talk show. During the show, he accused the politician number 2 for the poor state of the country. Naturally, in the second episode of the show the guest was politician number 2. The talk show host told his guest that politician number 1 accused him and politician number 2 then blamed some other politician. The newly blamed politician was the guest in the next show where the host told him that…

Even today, after almost 20 years, a new politician is a guest in each episode of the show where he is being told by whom he was accused for the poor state in the country. That politician then blames another politician and the vicious cycle continues. To make things more interesting, we have exclusively found out that each politician has a fixed strategy on how to behave during the show. More precisely, each politician knows who to blame based on the person who blamed him in the previous show. We will provide you with this information and hope you will be able to write a program that calculates what politician will be the guest of the $K$-th show.

Input

The first line contains integers $N$ $(2\le N\le 500)$ and $K$ $(1\le K\le {10}^{18})$ from the task description.

The $i$-th of the next $N$ lines contains $N$ integers where $j$-th integer tells us who will be blamed by the $i$-th politician if he was blamed by politician number $j$ in the last show.

You can assume that no politician will ever blame himself. Therefore, none of the numbers in $i$-th line of matrix will be equal to $i$. Similarly, note that the $i$-th number in the $i$-th matrix row will always be equal to $0$ and can be disregarded.

Output

In a single line you should output the number of a politician that will be the guest of the $K$-th episode of the talk show.

Scoring

In the test cases worth a total of $35$ points, it will hold $1\le K\le {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