呢題係一題交互題。
繼 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