Description

这是一道 IO 类交互题。详见 Notes 查看注意事项。

有一个 $n \times m$ 的矩阵 $a$。这个矩阵有一些特殊的性质：

• $\forall 1 \leq k \leq n, \forall 1\leq i < j \leq m,a_{k,i} \leq a_{k,j}$
• $\forall 1 \leq k \leq m, \forall 1\leq i < j \leq n,a_{i,k} \leq a_{j,k}$

你不知道具体的矩阵 $a$ 是多少。你需要找到一个矩阵中的神秘数字 $v$ 所在的位置（矩阵中可能存在多个 $v$，找到任意一个即可）。你可以提出若干个问题，最终得分将由你的询问次数决定。每次提问，你可以询问一个点 $\left(x,y\right)$，交互库会回答你矩阵中的该元素与 $x$ 的大小比较情况。在得知当前位置元素等于 $v$ 时，即找到了该元素。

一个测试点有 $T$ 组交互。

Constraints

• $T \le 10$
• $1 \leq n \leq 300$
• $1 \leq m \leq 300$
• $\exists 1\leq x \leq n,1 \leq y \leq m,a_{x,y}=v$
• 输入的数据均为整数。

根据你提出问题的数量，得分会有所不同。

设你提出的问题数量为 $k$，我们将先计算你的得分因子 $F(k)$：

$$F(k)=0.37^{\frac{k}{n + m - 1} - 1}$$

假设该组数据的满分为 $t$，则你在该组数据得到的分数 $S(k)$ 为：

$$S(k)= \begin{cases} t, & F(k) \ge 1, \\ t\cdot F(k), & 0.008\le F(k) \lt 1, \\ 0, & F(k) \lt 0.008 \end{cases} $$

你在整个测试点的得分即为 $\sum S(k)$。

另外，部分测试点有特殊性质，具体地：

分值占比	数据限制
$15\%$	$n\le 6,m\le 6$
$85\%$	无额外限制

Interaction

本题的一个测试点中包含多组数据，因此每个测试点的第一行是数据组数 $T$：

$\boxed{\begin{aligned} & T \end{aligned}}$

每组数据的交互格式如下：

初始时，你需要从标准输入中得到 $n$ 和 $m$ 的值：

$\boxed{\begin{aligned} & n {\quad} m \end{aligned}}$

接下来，你可以提出若干个问题。每个问题按如下格式，输出到标准输出：

$\boxed{\begin{aligned} & x {\quad} y \end{aligned}}$

应满足 $1 \leq x \leq n, 1 \leq y \leq m$。

交互库会将 $a_{x,y}$ 与 $v$ 进行比较。

如果 $a_{x,y}<v$，交互库会返回 <。

$\boxed{\begin{aligned} & \texttt{<} \end{aligned}}$

如果 $a_{x,y}>v$，交互库会返回 >。

$\boxed{\begin{aligned} & \texttt{>} \end{aligned}}$

如果 $a_{x,y}=v$，交互库会返回 =。此时你应该立即结束这组交互。

$\boxed{\begin{aligned} & \texttt{=} \end{aligned}}$

交互库还可能返回 !，这代表你的询问不合法。你应该立即结束这组交互，进入下一次交互。你的这组交互记 $0$ 分。

特别地，若你当前询问次数 $k$ 满足 $\forall x\ge k$，都有 $S(k)=0$，交互库也会返回 !。

$\boxed{\begin{aligned} & \texttt{!} \end{aligned}}$

Notes

本题的时间限制包括交互库的运行时间，若你的程序（不计算 IO 交互）不可以 $0.5\text{s}$ 内运行完毕，则不保证能通过本题。

每次输出后，请立即输出换行符并刷新标准输出缓冲区。 否则可能得到 TLE 或 WA 的评测结果。

一般来说，如果你不会操作文件系统：

• 对于 C 语言，fflush(stdout) 可以刷新标准输出缓冲区（下文简称缓冲区），C++ 当然也可以使用这种方法。
• 对于 C++，可选的操作较多（以下内容默认你在 namespace std 下）：
  • 当你用 cout << endl 时，会输出换行符并立即刷新缓冲区；
  • 当你使用 cout << flush 时，会立即刷新缓冲区；
  • 当你使用 cout.flush() 时，也会立即刷新缓冲区。
• 对于 Java，可以使用输出流的 flush 函数，如 System.out.flush()。
• 对于 Python，可以使用 sys.stdout.flush()，或者在调用 print 时指定参数 flush=True。
• 对于 Pascal，可以使用 flush(output)。
• 对于 Rust，使用 io::stdout().flush()。

其他语言的使用者请自行查阅相关文档。

接收到 = 或 ! 后，请立即进行下一组交互。否则，评测结果可能出现错误。

交互库是自适应的，即矩阵 $a$ 和目标数字 $v$ 可能在交互过程中变化，但是总是满足先前的所有询问。

Sample Interaction

假设 $v = 18$，矩阵 $a$ 如下。

$$\left[\begin{matrix} 1&2&3&5&21\\ 4&12&18&23&27\\ 9&13&36&39&39\\ 16&19&40&50&60 \end{matrix}\right] $$

输入	输出	解释
1		输入数据组数 $T=1$。
4 5		输入 $n=4,m=5$。
	1 2	你猜测了 $\left(1,2\right)$。
<		$a_{1,2}=4<v$，所以交互库返回 <。
	3 4	你猜测了 $\left(3,4\right)$。
>		$a_{3,4}=39>v$，所以交互库返回 >。
	2 3	你猜测了 $\left(2,3\right)$。
=		$a_{2,3}=18=v$，所以交互库返回 =。
		你的程序输入了 =，应当立即结束这组交互，进入下一组。现在没有下一组数据了，因此你的程序结束运行。
		上面的问题显然无法确定 $v$ 的具体位置。由于交互库是自适应的，$a$ 和 $v$ 可能会随时变化，评测结果可能会不同。