在一个完全虚构且极不现实的未知国家里，所有的政客不干实事，整天在国家电视台上互相指责。这一切都始于一个星期天的下午，1 号政客作为嘉宾参加了一档（现在非常火爆）脱口秀节目的第一期。在节目中，他指责 2 号政客导致了国家糟糕的现状。自然地，在节目的第二期中，嘉宾变成了 2 号政客。主持人告诉 2 号政客是 1 号政客指责了他，接着 2 号政客又指责了另一位政客。被指责的新政客则成为下一期节目的嘉宾，主持人也会告诉他同样的信息……

即使在近 20 年后的今天，每期节目依然会有一位新政客作为嘉宾，并被告知是谁指责了他导致国家现状糟糕。然后，该政客会指责另一位政客，如此循环往复。为了让事情更有趣，我们独家发现每个政客在节目中都有固定的应对策略。更具体地说，每个政客都会根据在上一期节目中指责他的人，来决定自己要指责谁。我们将为你提供这些信息，希望你能编写一个程序，计算出谁将成为第 $K$ 期节目的嘉宾。

输入格式

第一行包含两个整数 $N$（$2 \le N \le 500$）和 $K$（$1 \le K \le 10^{18}$），含义如题面所述。

接下来的 $N$ 行，每行包含 $N$ 个整数。其中第 $i$ 行的第 $j$ 个整数表示：如果 $i$ 号政客在上一期节目中被 $j$ 号政客指责，那么他接下来会指责谁。

你可以认为没有政客会指责自己。因此，矩阵第 $i$ 行中的数字都不会等于 $i$。类似地，注意矩阵第 $i$ 行的第 $i$ 个数字将始终为 $0$，可以忽略。

输出格式

输出单行一个整数，表示将作为该脱口秀第 $K$ 期节目嘉宾的政客编号。

子任务

在占总分 35 分的测试数据中，满足 $1 \le K \le 10^5$。

样例

输入样例 1

2 4
0 2
1 0

输出样例 1

2

输入样例 2

3 7
0 3 2
3 0 3
2 1 0

输出样例 2

1

输入样例 3

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

输出样例 3

3