#P2304I. Oh, no! Where is baby O?

Oh, no! Where is baby O?

本题没有可用的提交语言。

背景

这是一道交互题。如果你没有尝试过本类型的题,请移步新手村训练题单的最后两题。

注意,在使用非 C\mathtt{C} 语言(不包括 C++\mathtt{C++})提交时,请在输出之后,加一行 flush\mathtt{flush}

下面给出 C,C++,Java,Python\mathtt{C, C++, Java, Python} 的输出方式:

  1. C\mathtt{C}

    printf("! 233");
    
  2. C++\mathtt{C++}

    cout << "!" << 233 << '\n';
    cout.flush();
    
  3. Java\mathtt{Java}

    System.out.println("! 233");
    System.out.flush();
    
  4. Python\mathtt{Python}

    print("! 233")
    stdout.flush()
    

说明

Ocean 最近开发了一个游戏,名叫 "O宝去哪儿了"。

游戏将在一个 n×mn \times m 的矩阵上进行,并会将 O宝 置于一个未知的格子中。

作为玩家,你无法查看矩阵上的情况,只能进行下面的猜测:

  1. 玩家在系统中输入一个格子的横纵坐标,代表玩家的询问;
  2. 系统会按一种 步数最小 的方案 模拟 移动 O宝,并在模拟移动结束后给玩家一个数字,代表 O宝移动的步数。 注意,在模拟移动结束后,O宝会瞬移回原来的格子。
  3. 如果玩家可以判断出 O宝 的具体位置,那么游戏结束,否则,重复上面两步的操作。

注意,在每次移动时,O宝 只能移动到其所在位置的 88 个方向相邻格子的任意一个,如下图的任意绿色格子:

image

显然,只要询问次数够多,猜测位置是很容易的。

所以,Ocean 想考考你,如何在最多 33 次询问里,确定 O宝 的具体位置呢?

交互

本题有多组测试用例。

首先,你需要读入一行整数 tt,代表测试用例的数量。

接下来,对于每个用例,你需要先读入一行两个整数 n,mn, m,代表矩阵的大小。

对于一次询问,输出 ? r c,代表输入系统的横纵坐标为 r, c。然后,你需要读入一个整数,代表 O宝 模拟走到点 (r, c) 的最少移动次数。

如果你输出了错误的格式,或者询问次数超过 33 次,那么你将立即得到 Wrong Answer 判定。

如果你确定了 O宝 的位置,请输出 ! r c,代表 O宝 位于点 (r, c)

注意上述所有坐标都要在矩阵内。

只要你的答案是正确的,你就会得到 Accepted 判定。

注意,如果你的输出格式不正确,将会被判定为 Wrong Answer

如果你没有在输出后 flush\mathtt{flush},你将会得到除 Accepted 之外的其他任意评测结果。

如果你还是不知道怎么交互,可以开翻译阅读一下 codeforces 的官方介绍:

Interactive Problems: Guide for Participants - Codeforces

样例

样例输入1

2
3 4

1

2

5 3

3

1

2

样例输出1

? 2 3

? 2 4

! 2 2

? 2 2

? 5 2

? 5 3

! 5 1

样例解释1

在第一个测试用例中,O宝位于 (2,2)(2, 2)

玩家给出了询问 (2,3)(2, 3),走到该蓝色格子的最短步数是 11

玩家给出了询问 (2,4)(2, 4),走到该紫色格子的最短步数是 22

image

请注意,样例的询问方式和游玩方式似乎很愚蠢,所以它也许只是一个形象化的例子。

提示

1t1031 \leq t \leq 10 ^ 3

1n,m1091 \leq n, m \leq 10 ^ 9