CF1838F.Stuck Conveyor

This is an interactive problem.

There is an $n$ by $n$ grid of conveyor belts, in positions $(1, 1)$ through $(n, n)$ of a coordinate plane. Every other square in the plane is empty. Each conveyor belt can be configured to move boxes up ('^'), down ('v'), left ('<'), or right ('>'). If a box moves onto an empty square, it stops moving.

However, one of the $n^2$ belts is stuck, and will always move boxes in the same direction, no matter how it is configured. Your goal is to perform a series of tests to determine which conveyor belt is stuck, and the direction in which it sends items.

To achieve this, you can perform up to $25$ tests. In each test, you assign a direction to all $n^2$ belts, place a box on top of one of them, and then turn all of the conveyors on.

One possible result of a query with $n=4$. In this case, the box starts at $(2, 2)$. If there were no stuck conveyor, it would end up at $(5, 4)$, but because of the stuck '>' conveyor at $(3, 3)$, it enters an infinite loop.

The conveyors move the box around too quickly for you to see, so the only information you receive from a test is whether the box eventually stopped moving, and if so, the coordinates of its final position.

Interaction

You begin the interaction by reading a single integer $n$ ($2 \le n\le 100$) — the number of rows and columns in the grid.

Then, you can make at most $25$ queries.

Each query should begin with a line of the form ? r c, where r and c are the initial row and column of the box, respectively.

The next $n$ lines of the query should contain $n$ characters each. The $j$th character of the $i$th row should be one of '^', 'v', '<', or '>', indicating the direction of conveyor $(i, j)$ for this query.

After each query, you will receive two integers $x$ and $y$. If $x = y = -1$, then the box entered an infinite loop. Otherwise, its final position was $(x, y)$.

If you make too many queries or make an invalid query, you will receive the Wrong Answer verdict.

After you have found the stuck conveyor and its direction, print a single line ! r c dir, where r and c are the row and column of the stuck conveyor, respectively, and dir is one of '^', 'v', '<', or '>', indicating the direction of the stuck conveyor. Note that printing this answer does not count towards your total of $25$ queries. After printing this line, your program should terminate.

The interactor is non-adaptive. This means that the location and direction of the stuck belt is fixed at the start of the interaction, and does not change after the queries.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

Hacks

To make a hack, use the following format.

The first line should contain a single integer $n$ ($1 \le n \le 100$) — the number of rows and columns in the grid.

The next line should contain two integers $r$ and $c$ ($1 \le r, c \le n$), as well as a character $\mathrm{dir}$ ($\mathrm{dir}$ is one of '^', 'v', '<', '>') — the position of the stuck conveyor and its fixed direction. These values should be separated by spaces.

这是一个交互式问题。

存在一个 $n \times n$ 的传送带网格，位于坐标平面上位置 $(1, 1)$ 到 $(n, n)$ 的方格中。平面上其余所有方格均为空。每个传送带可被配置为将箱子向上（'^'）、向下（'v'）、向左（'<'）或向右（'>'）移动。若箱子移动到一个空方格上，则它将停止移动。

然而，在这 $n^2$ 个传送带中，恰好有一个是卡住的（stuck），无论你如何配置它，它始终以固定方向传送箱子。你的目标是通过一系列测试，确定哪个传送带是卡住的，以及它固定传送的方向。

为此，你最多可执行 $25$ 次测试。每次测试中，你为全部 $n^2$ 个传送带指定方向，将一个箱子放置在其中一个传送带上，然后启动所有传送带。

一个 $n=4$ 时查询的可能结果示例。本例中，箱子起始于 $(2, 2)$。若无卡住的传送带，它将最终停在 $(5, 4)$；但由于位于 $(3, 3)$ 处的卡住的 '>' 传送带，它陷入无限循环。

传送带移动箱子的速度过快，你无法实时观察其路径，因此每次测试你仅能获得如下信息：箱子是否最终停止移动；若停止，其最终位置坐标 $(x, y)$ 是多少。

交互流程

程序开始时，先读入一个整数 $n$（$2 \le n \le 100$），表示网格的行数与列数。

随后，你最多可进行 $25$ 次查询。

每次查询应以形如 ? r c 的一行开始，其中 r 和 c 分别为箱子初始所在的行号与列号。

接下来的 $n$ 行每行包含 $n$ 个字符。第 $i$ 行的第 $j$ 个字符应为 '^'、'v'、'<' 或 '>' 中的一个，表示本次查询中传送带 $(i, j)$ 的方向。

每次查询后，你将收到两个整数 $x$ 和 $y$。若 $x = y = -1$，则表示箱子进入了无限循环；否则，其最终位置为 $(x, y)$。

若你发出过多查询，或发出非法查询，将得到“Wrong Answer”判定。

当你确定了卡住的传送带的位置及其方向后，请输出一行 ! r c dir，其中 r 和 c 分别为该卡住传送带的行号与列号，dir 为 '^'、'v'、'<' 或 '>' 中的一个，表示其固定方向。注意：输出该答案不计入 $25$ 次查询总数。输出该行后，你的程序必须终止。

评测器是非自适应的（non-adaptive）。这意味着卡住传送带的位置和方向在交互开始时即已固定，且不会随查询而改变。

每次输出查询后，请务必输出换行符并刷新输出缓冲区。否则你将收到“Idleness limit exceeded”判定。实现方式如下：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请参阅相应文档。

Hack 输入格式

要构造 Hack 数据，请使用如下格式：

第一行应为一个整数 $n$（$1 \le n \le 100$），表示网格的行数与列数。

第二行应包含两个整数 $r$ 和 $c$（$1 \le r, c \le n$），以及一个字符 $\mathrm{dir}$（$\mathrm{dir}$ 为 '^'、'v'、'<' 或 '>' 中的一个），分别表示卡住传送带的位置及其固定方向。三者之间用空格分隔。

For the first query of the first sample input, the box starts on $(2, 2)$ and enters an infinite loop containing rows $2$ and $3$. Because the stuck conveyor is in row $1$, it does not affect the outcome of the query.

For the second query of the first sample input, the conveyors are configured in the same way, but the box starts on $(1, 1)$. If there were no stuck conveyor, it would enter an infinite loop between $(1, 2)$ and $(1, 3)$. However, the stuck conveyor redirects it to $(0, 2)$.

After these two queries, the program is able to determine that the stuck conveyor is at $(1, 2)$ and directs items upward.

The query for the second sample input corresponds to the picture above. After asking the query, there are many possibilities for the stuck conveyor, but the program correctly guesses that it is at $(3, 3)$ and directs items to the right.

对于第一个样例输入的第一个查询，箱子起始于 $(2, 2)$，并进入一个包含第 $2$ 行和第 $3$ 行的无限循环。由于卡住的传送带位于第 $1$ 行，因此它不影响该查询的结果。

对于第一个样例输入的第二个查询，传送带的配置方式相同，但箱子起始于 $(1, 1)$。若不存在卡住的传送带，它将在 $(1, 2)$ 和 $(1, 3)$ 之间进入无限循环。然而，卡住的传送带将其重定向至 $(0, 2)$。

在这两次查询之后，程序能够确定卡住的传送带位于 $(1, 2)$，且其方向为向上。

第二个样例输入的查询对应于上方图片所示情形。在提出该查询后，卡住的传送带有多种可能位置，但程序正确推断出它位于 $(3, 3)$，且其方向为向右。