Finding a Basin

The May Day holiday has arrived. To escape the tense and busy life of studying and to seek some long-awaited excitement, Xiaoqiang plans to go on an adventure with his friends in Adventure City. Adventure City is a square region with side length $n$, artificially divided into $n \times n$ small regions, where each small region is a unit square. For convenience, we define the coordinates of the small region in the $i$-th row and $j$-th column as $(i, j)$. We say two small regions $(x_1, y_1)$ and $(x_2, y_2)$ are adjacent if and only if they share a common edge, i.e., $|x_1 - x_2| + |y_1 - y_2| = 1$. Each small region has an elevation (represented by a real number), and the elevations of different small regions are distinct.

Xiaoqiang wants to find a basin in these $n \times n$ small regions, which is a small region that has a lower elevation than all its adjacent small regions. Adventure City is surrounded by a high wall, so a basin can appear on the edge, in which case it only needs to be lower than its three adjacent small regions; a basin can even appear at a corner, in which case it only needs to be lower than its two adjacent small regions.

There is a terrain query system at the entrance of Adventure City. Each query allows you to input two different small regions, and the system will tell you which one has a higher elevation. Since the query speed is very slow, Xiaoqiang wants to find a basin using as few queries as possible. Can you help him design a strategy?

Interaction

This is an interactive problem. Your program must interact with the testing library and must not access any files (including temporary files). The testing library provides several functions, whose usage and roles are as follows:

• init: Must be called first, and only once, to initialize the testing library.
• get_n: Returns the side length $n$ of Adventure City.
• query(x1, y1, x2, y2): Queries the relative elevation of small regions $(x_1, y_1)$ and $(x_2, y_2)$. If $(x_1, y_1)$ is higher than $(x_2, y_2)$, it returns $1$; otherwise, it returns $-1$.
• answer(x, y): Reports the result to the testing library, where $(x, y)$ is the coordinate of the basin you found. After this function is called, the testing library will automatically terminate your program.

Implementation Details

For Pascal users: Your program should reference the testing library using the following statement: uses basin_lib_p; The function prototypes provided by the testing library are: procedure init; function get_n: longint; function query(x1, y1, x2, y2: longint): longint; procedure answer(x, y: longint);

For C/C++ users: You should create a project, include the file basin_lib_c.o, and add the following line at the beginning of your program: #include "basin_lib_c.h" The function prototypes provided by the testing library are: void init(); int get_n(); int query(int, int, int, int); void answer(int, int);

Testing Your Program

• Create a file named basin.in in the working directory. The first line of the file contains an integer $n$, the side length of Adventure City. The following $n$ lines each contain $n$ real numbers, representing the elevation of each small region.
• Execute your program. The testing library will generate an output file basin.log, which contains the record of the interaction between your program and the library, as well as the final result.
• If the program terminates normally, the last line of basin.log contains an integer representing the number of queries you made.
• If the program terminates illegally, we do not guarantee that the content of basin.log is meaningful.
• During official testing, the testing library will generate the terrain itself and will try to make each answer as unfavorable to you as possible.

Constraints

• $2 \le n \le 63$

Examples

Input 1

3
9.1 1.2 7.3
5.4 2.5 3.6
6.7 8.8 4.9

Output 1

A possible full-score calling sequence is as follows:

Note: This example is only for illustrating the use of library functions and has no algorithmic significance.

Subtasks

If your program meets any of the following conditions, the test case receives 0 points: Accessed any file (including temporary files) or terminated on its own; Illegal call to library functions; Caused the testing library to terminate abnormally; The number of queries exceeds 200.

Otherwise, the test case receives full marks.