310470: CF1838F. Stuck Conveyor

F. Stuck Conveyortime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

ExamplesInput

3




-1 -1




0 2

Output

? 2 2
>><
>>v
^<<

? 1 1
>><
>>v
^<<

! 1 2 ^

Input

4





-1 -1

Output

? 2 2
v>v<
^v<v
v>v^
>v>v

! 3 3 >

Note

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.

题目大意：这是一个交互式问题。有一个n×n的传送带网格，位于坐标平面的(1, 1)到(n, n)位置。平面上的其他方格都是空的。每个传送带可以设置为向上(^)、向下(v)、向左(<)或向右(>)移动箱子。如果一个箱子移动到空方格上，它将停止移动。然而，n²个传送带中有一个是卡住的，无论怎样设置，它都会始终朝同一个方向移动箱子。你的目标是进行一系列测试，以确定哪个传送带卡住了，以及它发送物品的方向。

为了实现这一点，你可以进行最多25次测试。在每次测试中，你为所有n²个传送带分配一个方向，将一个箱子放在其中一个传送带上，然后打开所有传送带。

输入输出数据格式：你首先读取一个整数n（2≤n≤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次查询总数。打印这个行后，你的程序应该终止。

交互器是非适应性的。这意味着卡住传送带的位置和方向在交互开始时固定，并且在查询后不会改变。

样本测试：

输入：
3
? 2 2
>>
>>v
^<<
? 1 1
>>
>>v
^<<

输出：
! 1 2 ^

输入：
4
? 2 2
v>v<
^v v>v^
>v>v

输出：
! 3 3 >题目大意：这是一个交互式问题。有一个n×n的传送带网格，位于坐标平面的(1, 1)到(n, n)位置。平面上的其他方格都是空的。每个传送带可以设置为向上(^)、向下(v)、向左(<)或向右(>)移动箱子。如果一个箱子移动到空方格上，它将停止移动。然而，n²个传送带中有一个是卡住的，无论怎样设置，它都会始终朝同一个方向移动箱子。你的目标是进行一系列测试，以确定哪个传送带卡住了，以及它发送物品的方向。 为了实现这一点，你可以进行最多25次测试。在每次测试中，你为所有n²个传送带分配一个方向，将一个箱子放在其中一个传送带上，然后打开所有传送带。 输入输出数据格式：你首先读取一个整数n（2≤n≤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次查询总数。打印这个行后，你的程序应该终止。 交互器是非适应性的。这意味着卡住传送带的位置和方向在交互开始时固定，并且在查询后不会改变。 样本测试： 输入： 3 ? 2 2 >> >>v ^<< ? 1 1 >> >>v ^<< 输出： ! 1 2 ^ 输入： 4 ? 2 2 v>v< ^vv^ >v>v 输出： ! 3 3 >