Description

There are $n$ people who criticize each other.

You are also given a matrix $A$.

The rules are as follows:

• For the first time, person $1$ criticizes person $2$.

• If at the $(i-1)$-th time, person $u$ criticizes person $v$,

  then at the $i$-th time, person $v$ criticizes person $A_{v,u}$.

Find who is doing the criticizing at the $k$-th time (note: not the person being criticized).

Input Format

The first line contains two positive integers, $n$ and $k$.

The next $n$ lines contain the matrix $A$. The main diagonal of the matrix (the diagonal from top-left to bottom-right) is all $0$, and all other entries are positive integers from $1$ to $n$.

Output Format

Output one line containing your answer.

2 4
0 2
1 0

2

3 7
0 3 2
3 0 3
2 1 0

1

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

3

Hint

Constraints

• For $35$ pts of the testdata, it is guaranteed that $1 \leq k \leq 10^5$.
• For all testdata, $2 \leq n \leq 500$ and $1 \leq k \leq 10^{18}$.

Notes

This problem is translated from COCI2019-2020 CONTEST #5 T2 Političari, translated by 90693。

Translated by ChatGPT 5