Description

For a high-load system like Lutece, it is necessary to schedule multiple people on duty to ensure stability. In 3202, Lutece becomes very popular, and there are $n$ system engineers responsible for its maintenance, numbered from $1$ to $n$.

There is a duty roster denoted by $a_{i,j}$. On the first day, Engineer $1$ is on duty, and on the second day, Engineer $2$ is on duty. For each day starting from the second day, if Engineer $i$ is on duty today and Engineer $j$ was on duty yesterday, then Engineer $a_{i,j}$ will be on duty tomorrow. The duty roster is pre-planned in such a way that the engineer on duty today will not be on duty tomorrow.

The question is: Who is on duty on the $m$-th day?

Input

The first line contains two integers $n,m\ (3\le n\le 500, 1\le m\le 10^{18})$, indicating the number of engineers and the day we want to know.

For the next $n$ lines, each line contains $n$ integers, representing the duty roster $a_{i,j}\ (0 \le a_{i,j} \le n)$. It is guaranteed that only the numbers on the diagonal are $0$, i.e. only $a_{i,i}=0\ (1\le i\le n)$.

Output

Output one integer $x$, indicating Engineer $x$ will be on duty on the $m$-th day.

Samples

3 7
0 3 2
3 0 3
2 1 0

1

Note

For the example:

1. On the second day, Engineer $a_{2,1}=3$ will be on duty tomorrow, i.e. the third day, since Engineer $2$ is on duty today and Engineer $1$ was on duty yesterday.
2. On the third day, Engineer $a_{3,2}=1$ will be on duty tomorrow, i.e. the fourth day, since Engineer $3$ is on duty today and Engineer $2$ was on duty yesterday.

Resources

电子科技大学第十四届 ACM 趣味程序设计竞赛