CF2159F Grand Finale: Snakes

这是一个交互式问题。 给定一个整数 $n$ 以及一个 $n \times n$ 的数字网格 $G$。该数字网格包含了 $1$ 到 $n^2$ 的所有数字各一次。 我们定义长度为 $l$ 的蛇为一个双端队列 $[(x_1,y_1), (x_2,y_2), \ldots, (x_l,y_l)]$，其中 $(x_1,y_1)$ 是蛇头，$(x_l,y_l)$ 是蛇尾。在第 $1$ 秒时，$x_1=x_2=...=x_l=1$，且对所有的 $1 \leq i \leq l$，有 $y_i = i$。换句话说，蛇完全位于第一行，蛇头在 $(1,1)$，其余部分依次向右排列。 之后的每一秒，蛇可以向下或向右移动。具体地，蛇尾 $(x_l,y_l)$ 被移除，同时在头部添加 $(x_1+1,y_1)$ 或 $(x_1,y_1+1)$。蛇的第一次移动总是向下。可以证明，按照这些限制，蛇不会与自身相交。蛇将恰好移动 $2n-2$ 次，且始终不会离开网格。在第 $2n-1$ 秒时，蛇头到达 $(n,n)$，移动结束。可以证明，蛇一定恰好向右移动 $n-1$ 次，向下移动 $n-1$ 次。 共有 $n$ 条隐藏的蛇，第 $i$ 条蛇的长度为 $i$，其中 $1 \leq i \leq n$，它们相互独立地按上述规则移动。你并不知道蛇的具体移动方式。记 $f(l,T)$ 表示长度为 $l$ 的蛇在第 $T$ 秒所覆盖的方格中的最大数字。 如下图所示是长度 $l=3$ 的蛇的一个示例：  现在，给定一个整数 $m$，你需要找出 $f(l,T)$ 的最小的 $m$ 个值，并且询问 $f(l,T)$ 的总次数不超过 $120n+m$。

每个测试包含多组数据。第一行包含测试用例个数 $t$（$1 \le t \le 100$）。每组测试数据描述如下。 每组第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 500, 1 \leq m \leq n(2n-1)$）。 接下来 $n$ 行每行包含 $n$ 个整数 $G_{i,1}, G_{i,2}, \ldots, G_{i,n}$（$1 \leq G_{i,j} \leq n^2$）。 保证 $G$ 中每个数字 $1$ 到 $n^2$ 出现且只出现一次。 保证所有测试用例的 $n$ 之和不超过 $500$，$m$ 之和不超过 $5\times 10^4$。 读完 $n+1$ 行输入后，才可以开始你与评测机之间的交互，进行第一次询问。

无

下图展示了三条蛇移动时所覆盖的方格。  第一条蛇所覆盖的方格。  第二条蛇所覆盖的方格。 第三条蛇所覆盖的方格如描述中所示。 由 ChatGPT 5 翻译