给定一个大小为 $n \times n$ 的棋盘，包含 $n^2$ 个方格，我们用坐标 $(x, y)$ 来描述它们，其中 $x$ 是列号，$y$ 是行号（$1 \le x, y \le n$）。
在棋盘的某个方格 $(x_S, y_S)$ 上（我们不知道具体位置）站着一个骑士。我们可以提出如下形式的问题：“骑士从它所站的方格移动到坐标为 $(x, y)$ 的方格，最少需要多少步？”
骑士（俗称马）是一种国际象棋棋子，它总是向一个方向移动两格，再向垂直方向移动一格。因此，骑士在一步之内可以移动到八个方格中的任意一个（前提是该方格在棋盘范围内）。下图展示了骑士从标有字母 S 的方格出发，可以移动到的方格（用点标记）：
请编写一个程序，通过少量的问题猜出骑士的位置。
交互
你的程序将使用提供的库来回答提出的问题。要使用该库，你需要在程序中包含：
- C/C++:
#include "skolib.h" - Python:
from skolib import daj_n, pytanie, odpowiedz
该库提供以下函数：
daj_n()– 该函数返回一个整数 $n$，表示棋盘的大小。pytanie(x, y)– 该函数的返回值为骑士从 $(x_S, y_S)$ 移动到 $(x, y)$ 所需的最少步数。必须满足 $1 \le x, y \le n$。骑士在移动过程中不得离开棋盘。odpowiedz(xS, yS)– 该函数用于提交程序猜出的骑士位置。必须满足 $1 \le x_S, y_S \le n$。该函数必须且仅能调用一次。调用此函数后，程序将自动终止。如果提交的骑士位置错误，程序将以“错误答案”的结果终止。
库不需要在与你的程序交互开始时就确定骑士的位置。它可以在交互过程中改变位置，只要新位置仍然符合之前调用 pytanie 函数所返回的结果。
你的程序不得打开任何文件，也不得使用标准输入和输出。程序可以使用标准错误输出（stderr），但请记住，这会消耗宝贵的时间。
你的解决方案将通过以下命令与库一起编译：
- C++:
g++ -O3 -static -std=c++17 skolib.cpp sko.cpp - Python:
python3 sko.py
注意：上述内存限制仅适用于你的解决方案，不包括库所使用的内存。
子任务
测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。
| 子任务 | 条件 | 分值 |
|---|---|---|
| 1 | $4 \le n \le 10$ | 40 |
| 2 | $4 \le n \le 100$ | 20 |
| 3 | $4 \le n \le 1000$ | 40 |
如果 $m$ 是你的程序在给定测试用例中调用 pytanie 函数的次数，那么你的解决方案将获得该测试用例的以下百分比分数（如果超过时间限制的一半，则会相应缩减）：
| 调用次数 | 得分百分比 |
|---|---|
| $m \le 6$ | 测试用例的 100% 分数 |
| $7 \le m \le 12$ | $(85 - 5m)\%$ 的分数 |
| $13 \le m \le 22$ | $(46 - 2m)\%$ 的分数 |
| $23 \le m$ | 0% 的分数（结果为“错误答案”） |
样例
以下是示例测试的程序运行过程。
| 调用 | 结果 | 说明 |
|---|---|---|
daj_n() |
8 | $n = 8$ |
pytanie(1, 2) |
5 | |
pytanie(1, 7) |
4 | |
pytanie(8, 2) |
0 | |
pytanie(8, 7) |
3 | |
odpowiedz(8, 2) |
– | 使用 4 次提问得出正确答案，获得 100% 分数 |
下图展示了骑士从 $(8, 2)$ 到 $(1, 2)$ 的最短路径之一：
实现细节
示例错误解决方案及示例库位于 dlazaw 文件夹中。这些库的行为可能与最终评估解决方案时使用的库不同，且可能不满足题目要求。它们仅用于展示与程序的交互方式。
你的解决方案与示例库编译后，会从标准输入读取棋盘描述——首先是数字 $n$，然后是 $n$ 行，每行包含 $n$ 个数字，表示骑士到各个方格的距离。示例库使用这些距离来回答你程序提出的问题。