这是一道交互题，仅支持 C++ 语言提交。

UOJ NOI Round 2077 有 $n$ 天，每天有 $n$ 道题。第 $i$ 天的第 $j$ 道题难度是 $a_{i,j}$。每一天的题目难度都是不降的，而且对于同一位置的题，每天的这道题的难度也是不降的。也就是说，对于 $\mathrm{\forall }1\le x\le n,1\le y_1<y_2\le n$，都有 $a_{x,y_1}\le a_{x,y_2}$ 且 $a_{y_1,x}\le a_{y_2,x}$。

小重和小庆想要知道这 $n^2$ 道题中第 $k$ 简单的题的难度。然而，他们现在并不知道每道题的难度是什么。他们只能在比赛的 ${10}^6$ 天内，每天选出一道题并鉴定其难度。

题目保证所有 $a_{i,j}$ 是预先给定的，不会根据你的操作而动态生成。

实现细节

你需要引用头文件 #include "matrix.h"。你可以调用以下函数与交互库进行交互：

long long query(int x, int y);

• 这个函数会返回第 $x$ 天第 $y$ 题的难度。
• 你需要保证 $1\le x,y\le n$。
• 在一个测试点中，你最多可以调用该函数 ${10}^6$ 次。

你不需要，也不应该实现主函数。在本题中，你只需要实现如下函数：

long long solve(int n, long long k);

• 其中 $n$ 为比赛的天数和每天的题目数，函数的返回值应为所有 $a_{i,j}$ 中第 $k$ 小的值。
• 最终测试时，对于每个测试点，交互库会调用恰好一次 solve 函数，并根据函数的返回值是否正确来评分。

在选手目录（题目附件）中，我们提供了 sample.cpp 供你参考，你可以在此基础上实现你的程序。

测试程序方式

本题目录下提供了 grader.cpp 文件。最终测试的交互库与下发交互库有不同，因此你的实现不应依赖交互库实现。

你需要将你的程序 matrix.cpp 和 grader.cpp、matrix.h 放置在同一目录下，并在该目录下使用如下编译命令得到可执行程序 matrix(.exe)：

g++ -o matrix matrix.cpp grader.cpp -O2 -std=c++17

可执行程序从标准输入读入以下格式的数据：

• 第一行，共两个整数 $n,k$。
• 第二行一个整数 $type$ 表示数据生成方式。
• 如果 $type=0$，那么接下来输入 $n$ 行，每行 $n$ 个整数，表示每道题的难度。

在本地测试时，请务必保证你的输入格式符合要求，否则我们不保证交互库会正常运行。

如果你的输入合法且没有运行错误，下发的交互库将会根据你的调用输出如下信息：

• 如果某次 query 函数的调用违反了 $1\le x,y\le n$ 的限制或调用 query 次数超过 ${10}^6$ 次，输出错误信息：Wrong Answer 0!，并且交互库立即终止。
• 如果 solve 函数的返回值正确，那么交互库会输出三个数，依次表示：solve 函数的返回值，$n$ 的值，query 函数的调用次数。

你的程序不应该操作标准输入输出，否则视为攻击交互库。

样例一

input

3 5
0
1 2 5
3 4 6
7 8 9

output

5

样例二/三/四/五/六/七

见附件下载。

限制与约定

对于全部数据，保证 $1\le n\le 2\times {10}^5$，$1\le k\le n^2$，$0\le a_{i,j}\le {10}^{18}$。

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{1GB}}$

保证交互库的运行时间不超过 $\mathtt{\text{1s}}$，使用空间不超过 $\mathtt{\text{512MB}}$。