注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C
• C++

请在提交源代码前添加 #include "grader.h"。

题目描述

题目译自 JOISC 2013 Day3 T3 「山岳救助隊」

由于 IOI 山频频发生登山者遇难事故，IOI 国政府设立了专门的山岳救援队。成立几天后，救援队接到了一通报警，称有遇难者目前停留在高度为 $X$ 的位置。

IOI 山可以用一个纵向 $R$ 行、横向 $C$ 列的网格表示，每个格子都有一个确定的高度值。我们将上数第 $r$ 行、左数第 $c$ 列的格子记为 $(r, c)$。已知山的地形满足以下特点：

• 没有任何两个不同格子的高度值相同。
• 每个格子的高度为 $1$ 到 $1000000000$ 之间的整数。
• 格子 $(R_{S}, C_{S})$ 是山顶，即高度最大的格子。
• 定义两个格子 $(r_{1}, c_{1})$ 和 $(r_{2}, c_{2})$ 的距离为 $|r_{1} - r_{2}| + |c_{1} - c_{2}|$。对于相邻的两个格子（即共用一条边），距离山顶较远的格子高度较低。

由于山岳救援队刚成立，对 IOI 山的调查尚未完成，包括山顶在内，各格子的高度信息未知。救援队可以使用专业测量设备查询指定格子的高度，但每次查询需耗费一定时间。你的任务是使用测量设备定位高度为 $X$ 的遇难者所在格子，且测量设备的使用次数需控制在 $1000$ 次以内。

给定表示 IOI 山网格大小的整数 $R, C$、山顶位置 $R_{S}, C_{S}$ 以及遇难者所在格子高度 $X$，你需要编写一个程序，使用最多 $1000$ 次测量设备定位遇难者所在格子。

输入格式

你需要编写一个程序，使用测量设备的方式如下： 程序必须实现以下函数：

• void Rescue(int R, int C, int RS, int CS, int X)

  该函数在每个测试用例中仅调用一次。参数 $R, C$ 分别表示山网格的纵向和横向大小，$RS, CS$ 分别表示山顶的行号和列号 $R_{S}, C_{S}$，$X$ 表示遇难者所在格子的高度 $X$。

程序中可以调用以下函数：

• int Measure(int RM, int CM)

  该函数用于调用测量设备，参数 $RM, CM$ 分别表示要测量高度的格子行号和列号 $R_{M}, C_{M}$，需满足 $1 \leq R_{M} \leq R, 1 \leq C_{M} \leq C$。函数返回值是格子 $(R_{M}, C_{M})$ 的高度（$1$ 到 $1000000000$ 之间的整数）。 若以不满足 $1 \leq R_{M} \leq R, 1 \leq C_{M} \leq C$ 的参数调用此函数，将被判为 Wrong Answer [1]，程序执行终止。 若此函数调用次数超过 $1000$ 次后再次调用，将被判为 Wrong Answer [2]，程序执行终止。

• void Pinpoint(int RP, int CP)

  该函数在确定遇难者所在格子时仅调用一次，参数 $RP, CP$ 分别表示确定的遇难者所在格子的行号和列号 $R_{P}, C_{P}$，需满足 $1 \leq R_{P} \leq R, 1 \leq C_{P} \leq C$。此函数无返回值。 若以不满足 $1 \leq R_{P} \leq R, 1 \leq C_{P} \leq C$ 的参数调用此函数，将被判为 Wrong Answer [3]，程序执行终止。 调用此函数时，若格子 $(R_{P}, C_{P})$ 的高度等于 $X$，则判为正确答案；否则判为 Wrong Answer [4]，程序执行终止。 若 Rescue 函数未调用此函数即结束，则判为 Wrong Answer [5]，程序执行终止。

编译与运行

用于测试你程序的示例测评程序包含在可以从「文件」中获取。该文件也包含需提交的文件样例。

示例测评程序由一个文件组成，文件名为 grader.c 或 grader.cpp。要测试你的程序，可按以下命令执行：

• 对于 C： gcc -O2 -lm grader.c mountain.c -o grader
• 对于 C++： g++ -O2 grader.cpp mountain.cpp -o grader

编译成功后，将生成名为 grader 的可执行文件。 注意，实际测评程序与示例测评程序可能不同。此程序从标准输入读取输入，并将结果输出到标准输出。

输入格式

示例测评程序从标准输入读取以下数据：

• 第一行包含五个整数 $R, C, R_{S}, C_{S}, X$，用空格分隔，分别表示山网格的纵向大小 $R$、横向大小 $C$、山顶格子 $(R_{S}, C_{S})$、遇难者所在格子高度 $X$。
• 接下来 $R$ 行描述山的高度信息，第 $i$ $(1 \leq i \leq R)$ 行包含 $C$ 个整数，其中第 $j$ $(1 \leq j \leq C)$ 个整数表示格子 $(i, j)$ 的高度。

输出格式

若程序正常执行结束，示例测评程序将向标准输出输出一行信息：

• 若正确，则输出 Accepted。
• 若不正确，则根据“实现细节”部分的编号输出类似 Wrong Answer [1] 的信息。 特别地，对于 Wrong Answer [4]，会额外输出正确遇难者位置 $(R_{X}, C_{X})$ 及 Pinpoint 函数调用时指定的格子 $(R_{P}, C_{P})$，格式如 Wrong Answer [4]: (RX, CX)=(3,2), (RP, CP)=(4,1)。

样例

示例测评程序读取的输入示例及相应的函数调用示例如下：

输入数据：

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

函数调用与返回值：

注意，此示例中的函数调用不一定具有实际意义。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq R \leq 200$
• $1 \leq C \leq 200$
• $1 \leq R_{S} \leq R$
• $1 \leq C_{S} \leq C$
• $1 \leq X \leq 1000000000$

详细子任务附加限制及分值如下表所示。