题目描述

有 $n$ 个人互相批评。

另提供矩阵 $A$。

规则如下：

• 第一次，第 $1$ 个人批评第 $2$ 个人。

• 如果第 $i-1$ 次为第 $u$ 个人批评第 $v$ 个人，

  那么第 $i$ 次为第 $v$ 个人批评第 $A_{v,u}$ 个人。

求第 $k$ 次是谁进行批评（注意：不是被批评）。

输入格式

第一行：两个正整数，$n$ 和 $k$。

以下 $n$ 行：矩阵 $A$。矩阵的主对角线（就是从左上到右下的那条对角线）全是 $0$，其他部分由从 $1$ 到 $n$ 的正整数组成。

输出格式

一行：你的答案。

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

提示

数据范围

• 对于 $35 pts$ 的数据，保证 $1\leq k\leq 10^5$。
• 对于所有的数据，$2\leq n\leq 500$ 且 $1\leq k\leq 10^{18}$。

说明

题目译自 COCI2019-2020 CONTEST #5 T2 Političari ，译者 90693。