P6867 [COCI 2019/2020 #5] Politicari

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).

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 one line containing your answer.

### 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](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #5](https://hsin.hr/coci/archive/2019_2020/contest5_tasks.pdf) _T2 Političari_**, translated by [90693](/user/90693)。 Translated by ChatGPT 5