The government of the IOI nation established a mountain rescue team specializing in Mount IOI due to the frequent accidents occurring there. A few days after its establishment, the rescue team received a report of an accident. According to the report, the victims are currently staying at a location with an altitude of $X$.
Mount IOI is represented as a grid with $R$ rows and $C$ columns, and an altitude value is determined for each cell. Let $(r, c)$ denote the cell in the $r$-th row from the top and the $c$-th column from the left. The shape of the mountain is known to satisfy the following conditions:
- There are no two distinct cells with the same altitude.
- The altitude of every cell is an integer between $1$ and $1\,000\,000\,000$, inclusive.
- The cell $(R_S, C_S)$ is the peak of the mountain. That is, the cell with the highest altitude is $(R_S, C_S)$.
- The distance between two cells $(r_1, c_1)$ and $(r_2, c_2)$ is defined as $|r_1 - r_2| + |c_1 - c_2|$. For any two adjacent cells, the one further from the peak has a lower altitude. Note that two cells are adjacent if they share an edge.
Since the rescue team was established only recently, the survey of Mount IOI is not complete, and the altitudes of the cells, including the peak, are unknown. You can use a specialized measuring instrument to check the altitude of a single cell by specifying its position, but it takes a certain amount of time to perform a measurement. You want to identify the position of the cell with altitude $X$ where the victims are located, but you must limit the number of times you use the measuring instrument to at most $1\,000$.
Task
Given the integers $R$ and $C$ representing the size of the grid, the position of the peak $(R_S, C_S)$, and the altitude $X$ of the cell where the victims are located, write a program to identify the position of the cell where the victims are located by using the measuring instrument at most $1\,000$ times.
Implementation Details
You must write a single program that implements the method of using the measuring instrument. Your program must implement the following routine:
void Rescue(int R, int C, int RS, int CS, int X)
This routine is called exactly once for each test case. The arguments $R$ and $C$ are the number of rows and columns of the grid representing the mountain, respectively. The arguments $R_S$ and $C_S$ are the row and column indices of the mountain's peak, respectively. The argument $X$ is the altitude of the cell where the victims are located.
In your program, you can call the following routines:
int Measure(int RM, int CM)
This routine is called when you want to use the measuring instrument. The arguments $R_M$ and $C_M$ are the row and column indices of the cell whose altitude you want to check, respectively. They satisfy $1 \le R_M \le R$ and $1 \le C_M \le C$. The return value of this routine is an integer between $1$ and $1\,000\,000\,000$, representing the altitude of the cell $(R_M, C_M)$.
If this routine is called with values that do not satisfy $1 \le R_M \le R$ and $1 \le C_M \le C$, it will be judged as Wrong Answer [1], and the program will be terminated.
Also, if this routine is called after it has already been called $1\,000$ times, it will be judged as Wrong Answer [2], and the program will be terminated.
void Pinpoint(int RP, int CP)
This routine is called exactly once when you have identified the cell where the victims are located. The arguments $R_P$ and $C_P$ are the row and column indices of the cell where you have identified the victims to be, respectively. They satisfy $1 \le R_P \le R$ and $1 \le C_P \le C$. This routine has no return value.
If this routine is called with values that do not satisfy $1 \le R_P \le R$ and $1 \le C_P \le C$, it will be judged as Wrong Answer [3], and the program will be terminated.
When the program calls this routine, if the altitude of the cell $(R_P, C_P)$ is equal to $X$, it will be judged as Correct; otherwise, it will be judged as Wrong Answer [4], and the program will be terminated.
If the Rescue routine terminates without calling this routine even once, it will be judged as Wrong Answer [5], and the program will be terminated.
Input
The sample grader reads the following input from standard input:
- The first line contains the integers $R, C, R_S, C_S, X$ separated by spaces, representing the height $R$ and width $C$ of the grid, the peak position $(R_S, C_S)$, and the altitude $X$ of the victims' location.
- The following $R$ lines contain information about the mountain's altitudes. The $i$-th line ($1 \le i \le R$) contains $C$ integers, where the $j$-th integer ($1 \le j \le C$) represents the altitude of the cell $(i, j)$.
Output
If the program terminates normally, the sample grader outputs the following information to standard output in one line:
- If correct, it outputs "Accepted".
- If incorrect, it outputs the type of error as "Wrong Answer[1]" based on the numbers written in the "Implementation Details" section. Furthermore, for Wrong Answer [4], the correct location of the victims $(R_X, C_X)$ and the information about the cell $(R_P, C_P)$ specified by the arguments when the
Pinpointroutine was called are output as "Wrong Answer[4] : (RX, CX) = (3, 2), (RP, CP) = (4, 1)".
Constraints
All input data satisfy the following conditions:
- $1 \le R \le 200$
- $1 \le C \le 200$
- $1 \le R_S \le R$
- $1 \le C_S \le C$
- $1 \le X \le 1\,000\,000\,000$
Subtasks
Subtask 1 [20 points]
Satisfies the following conditions:
- $R \le 50$
- $C \le 50$
Subtask 2 [80 points]
There are no additional constraints.
Examples
Example 1
Input:
5 5 3 3 76 14 59 84 62 28 15 73 92 76 35 68 97 100 89 75 58 67 86 79 55 17 25 71 10 5
| Call | Return Value |
|---|---|
Measure(1, 1) |
14 |
Measure(3, 5) |
75 |
Measure(2, 4) |
76 |
Pinpoint(2, 4) |
None |
Note that this example does not necessarily represent a meaningful sequence of routine calls.