A chessboard of size $n \times n$ consists of $n^2$ squares, which we describe using coordinates $(x, y)$, where $x$ is the column number and $y$ is the row number ($1 \le x, y \le n$).

A knight is located on one of the squares $(x_S, y_S)$ of this board (we do not know which one). We can ask questions of the form: "What is the minimum number of moves a knight needs to get from the square it is standing on to the square with coordinates $(x, y)$?"

A knight is a chess piece that always moves two squares in one direction and one square in the perpendicular direction. Thus, in one move, a knight can move to one of eight squares (provided, of course, that such a square is within the boundaries of the board). The figure below shows the possible moves of a knight from the square marked with the letter S to the squares marked with dots:

Write a program that guesses the knight's position using a small number of questions.

Interaction

Your program will use the provided library to answer the questions. To use the library, you must include the following in your program:

• C/C++: #include "skolib.h"
• Python: from skolib import daj_n, pytanie, odpowiedz

The library provides the following functions:

• daj_n() – The function returns an integer $n$, representing the size of the chessboard.
• pytanie(x, y) – The result of the function is the minimum number of moves the knight must make to go from square $(x_S, y_S)$ to square $(x, y)$. It must hold that $1 \le x, y \le n$. In no move can the knight leave the chessboard.
• odpowiedz(xS, yS) – This function allows you to report the knight's position guessed by the program. It must hold that $1 \le x_S, y_S \le n$. It must be called exactly once. After executing this function, the program will be automatically terminated. If the knight's position provided in the function is incorrect, the program will terminate with the verdict Wrong Answer.

The library does not have to determine the knight's position at the beginning of the interaction with your program. It may change the position during the interaction, as long as the new position is still consistent with the results returned by previous calls to the pytanie function.

Your program must not open any files or use standard input and output. It may use standard diagnostic output (stderr), but remember that this consumes valuable time.

Your solution will be compiled with the library using the following commands:

• C++: g++ -O3 -static -std=c++17 skolib.cpp sko.cpp
• Python: python3 sko.py

Note: The memory limit mentioned above applies only to your solution and therefore does not include the memory used by the library.

Evaluation

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

If $m$ is the number of calls to the pytanie function that your program made in a given test case, your solution will receive the following percentage of points for that test (scaled accordingly if half the time limit is exceeded):

Sample interaction

Input 1

daj_n() -> 8
pytanie(1, 2) -> 5
pytanie(1, 7) -> 4
pytanie(8, 2) -> 0
pytanie(8, 7) -> 3
odpowiedz(8, 2)

Note 1

The figure below shows one of the shortest paths for a knight from square $(8, 2)$ to square $(1, 2)$:

Evaluation tests

1ocen: $n = 10, x_S = 3, y_S = 7$; 2ocen: $n = 100, x_S = 3, y_S = 7$.

Experiments

Sample incorrect solutions along with sample libraries can be found in the dlazaw folder. The libraries may differ in behavior from those used for the final evaluation of solutions and may not meet the requirements of the task. They are only intended to show how to interact with the program.

Your solution compiled with the sample library reads the board description from standard input – the number $n$, and then $n$ lines containing $n$ numbers each, which are the distances of the knight to subsequent squares. The sample library uses these distances to answer your program's questions.