本題為互動題。
繼 2018 年至 2024 年取得巨大成功之後，南京航空航天大學（NUAA）將連續第八次舉辦國際大學生程式設計競賽（ICPC）南京區域賽。
Power of Two 隊與 Three Hold Two 隊分別在 2018 年和 2019 年為清華大學奪得冠軍頭銜。在 2020、2021 和 2022 年，來自北京大學的 Inverted Cross 隊奪得了三連冠；而在 2023 年，另一支來自北京大學的隊伍 Reborn as a Vegetable Dog 贏得了冠軍。2024 年則由來自浙江大學的 Afterlife 隊獲得第一名。
今年約有 $335$ 支隊伍參賽。比賽最多將頒發 $33$ 面金牌、$66$ 面銀牌與 $99$ 面銅牌（注意這些數字僅供參考）。我們十分期待看到參賽選手們的傑出表現！同時我們也想對所有為本次比賽辛勤付出的工作人員與志工表達謝意。感謝大家對本次比賽的巨大貢獻！
攝於 2023 ICPC 亞洲南京區域賽
在 2018 年的比賽中，問題 K Kangaroo Puzzle 要求參賽者為該遊戲構造一個操作序列：
謎題是一個有 $n$ 列與 $m$ 行（$1 \le n, m \le 20$）的網格，網格中站著若干隻（至少 $2$ 隻）袋鼠。玩家的目標是控制牠們聚集在一起。某些格子中有牆壁，袋鼠無法進入有牆的格子。其餘格子都是空的。袋鼠可以從一個空格移動到上、下、左、右四個方向的相鄰空格。
一開始每個空格中都恰好有一隻袋鼠，玩家可以透過按下鍵盤上的
U、D、L、R按鈕來控制袋鼠。所有袋鼠會根據你按下的按鈕同時移動。參賽者需要構造一個長度至多為 $5 \times 10^4$ 步且僅由
U、D、L、R構成的操作序列來達成目標。
在 2020 年的比賽中，問題 A Ah, It’s Yesterday Once More 要求參賽者構造一張輸入地圖，以 hack 上述問題的以下程式碼：
#include <bits/stdc++.h>
using namespace std;
string s = "UDLR";
int main()
{
srand(time(NULL));
for (int i = 1; i <= 50000; i++) putchar(s[rand() % 4]);
return 0;
}此外，在 2021 年比賽（問題 A，Oops, It’s Yesterday Twice More）、2022 年比賽（問題 A，Stop, Yesterday Please No More）、2023 年比賽（問題 A，Cool, It’s Yesterday Four Times More）以及 2024 年比賽（問題 A，Hey, Have You Seen My Kangaroo?）中，每年我們都有一道與袋鼠相關的題目！我們很想向大家介紹所有這些題目，但如果每年都這麼做，到了 3025 年比賽時，光是一道題目的題面就可能長達 500 頁。因此我們這次將它們省略。再說，你或許已經在練習賽中見過它們了。
現在，在 2025 年的比賽中，正如大家所預料的，袋鼠題又回來了！我們不知道為什麼出題者如此執著於袋鼠，但本次的問題如下：
給定一個有 $n$ 列與 $m$ 行的網格。在第 $i_h$ 列第 $j_h$ 行的格子中有一個洞。所有其他格子都是空的，且每個空格中都站著一隻袋鼠。
同樣地，袋鼠是透過按下鍵盤上的 U、D、L、R 按鈕來控制的。所有袋鼠會根據按下的按鈕同時移動。具體而言，對於位於第 $i$ 列第 $j$ 行、記作 $(i, j)$ 的任何袋鼠：
- 按鈕
U：牠會移動到 $(i - 1, j)$。 - 按鈕
D：牠會移動到 $(i + 1, j)$。 - 按鈕
L：牠會移動到 $(i, j - 1)$。 - 按鈕
R：牠會移動到 $(i, j + 1)$。
如果一隻袋鼠踏入洞中（即 $i = i_h$ 且 $j = j_h$）或走出網格之外，牠就會從網格中被移除。
問題在於，$i_h$ 與 $j_h$ 的確切值是未知的。你的任務是在最多 $(n + m + 10)$ 次詢問內找出洞的位置。每次詢問你可以按一個按鈕（U、D、L 或 R）。互動器會輸出一個整數 $t$ 作為回答，代表按下按鈕後網格中剩餘的袋鼠數量。
請注意，互動器不是自適應的（non-adaptive），這意味著每組測試資料的答案都是預先決定的。
輸入格式
有多組測試資料。輸入的第一行包含一個整數 $T$（$1 \le T \le 100$），代表測試資料的組數。對於每組測試資料：
第一行包含兩個整數 $n$ 與 $m$（$3 \le n, m \le 30$），代表網格的列數與行數。
互動協議
若要進行詢問，請輸出一行。首先輸出 ? 後接一個空格，接著輸出一個大寫英文字母（U、D、L 或 R）。在刷新輸出緩衝區後，你的程式應讀取一個整數 $t$，代表對你詢問的回答。請記住，每組測試資料最多只能進行 $(n + m + 10)$ 次詢問。
若你想猜測洞的位置，請輸出一行。首先輸出 ! 後接一個空格，接著輸出兩個以空格分隔的整數 $i_h$ 與 $j_h$（$1 \le i_h \le n$，$1 \le j_h \le m$）代表位置。刷新輸出緩衝區後，你的程式應繼續處理下一組測試資料，若沒有更多測試資料則立即結束程式。注意你的猜測不計入詢問次數。
若要刷新輸出緩衝區，你可以使用：
- C 與 C++ 中的
fflush(stdout)（若使用printf）或cout.flush()（若使用cout）。 - Java 與 Kotlin 中的
System.out.flush()。 - Python 中的
sys.stdout.flush()。
範例
2
3 4
7
3
4 3
8
5? L
? D
! 2 3
? U
? R
! 1 1