CF2159F.Grand Finale: Snakes

This is an interactive problem.

You are given an integer $n$ and an $n\times n$ grid of numbers $G$. The grid of numbers contains each number from $1$ to $n^2$ exactly once.

Let's define a snake of length $l$ as a deque $[(x_1,y_1), (x_2,y_2), \ldots, (x_l,y_l)]$, where $(x_1,y_1)$ is the head of the snake, and $(x_l,y_l)$ is the tail. At second $1$, $x_1=x_2=\ldots = x_l=1$ and $y_i=i$ for all $1 \leq i \leq l$. In other words, the snake is entirely located in the first row, with the head at $(1,1)$ and the rest of the snake to the right of the head.

Each subsequent second, the snake moves down or right in the grid. Formally, the tail $(x_l,y_l)$ is removed, and either $(x_1+1,y_1)$ or $(x_1,y_1+1)$ is added as the new head. The first move of the snake is always downwards. It can be shown that the snake will never intersect itself under these restrictions. The snake will move exactly $2n-2$ times, never moving outside the grid. At second $2n-1$, the head reaches $(n,n)$, and the movement stops. It can be shown that the snake moves exactly $n-1$ times to the right and exactly $n-1$ times downwards.

There are $n$ hidden snakes, with the $i$-th snake having length $i$ for $1 \leq i \leq n$, each moving independently according to the rule above. You do not know how the snakes move. Define $f(l,T)$ as the maximum number that the snake with length $l$ covers at second $T$.

An example of a snake with length $l=3$.

Now, you are also given an integer $m$. Your task is to find the $m$ smallest values of $f(l,T)$, using at most $120n+m$ queries asking for the value of $f(l,T)$ for some $1 \leq l \leq n$ and $1 \leq T \leq 2n-1$.

这是一个交互式问题。

你将得到一个整数 $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=\ldots = 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$ 个最小值，至多使用 $120n+m$ 次查询，每次查询形如：对某个 $1 \leq l \leq n$ 和 $1 \leq T \leq 2n-1$，询问 $f(l,T)$ 的值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 500, 1 \leq m \leq n(2n-1)$).

The following $n$ lines contain the grid $G$. The $i$-th of these lines contains $n$ integers $G_{i,1}, G_{i,2}, \ldots, G_{i,n}$ ($1 \leq G_{i,j} \leq n^2$).

It is guaranteed that $G$ contains each number from $1$ to $n^2$ exactly once.

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$, and the sum of $m$ over all test cases does not exceed $5\cdot 10^4$.

After you read the $n+1$ lines of input, the interaction begins with your first query.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 500,\ 1 \leq m \leq n(2n-1)$）。

接下来的 $n$ 行描述网格 $G$。其中第 $i$ 行包含 $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\cdot 10^4$。

在你读入前 $n+1$ 行输入后，交互部分即从你的第一个查询开始。

Below shows the tiles that the three snakes cover as they move across the grid.

The tiles covered by the first snake.

The tiles covered by the second snake.

The tiles covered by the third snake are shown in the statement above.

下方展示了三条蛇在网格上移动时所覆盖的方块。

第一条蛇所覆盖的方块。

第二条蛇所覆盖的方块。

第三条蛇所覆盖的方块已在题干上方给出。