これはインタラクティブ問題です。

2018 年から 2024 年までの大成功に続き、南京航空航天大学（NUAA）は 8 年連続で国際大学対抗プログラミングコンテスト（ICPC）南京地区大会を開催します。

2018 年と 2019 年には、チーム Power of Two とチーム Three Hold Two が清華大学に優勝をもたらしました。2020 年、2021 年、2022 年には北京大学のチーム Inverted Cross が 3 連覇を達成し、2023 年には同じく北京大学の別チーム Reborn as a Vegetable Dog が優勝しました。2024 年には浙江大学のチーム Afterlife が 1 位を獲得しました。

今年は約 $335$ チームがコンテストに参加しています。最大で金メダル $33$ 個、銀メダル $66$ 個、銅メダル $99$ 個が授与されます（これらの数値は参考値です）。参加者の皆さんの素晴らしいパフォーマンスを楽しみにしています！また、本大会のために尽力してくださったすべてのスタッフとボランティアの皆様に深く感謝いたします。本大会への多大な貢献をありがとうございます！

2023 ICPC Asia Nanjing Regional Contest にて撮影

2018 年のコンテストの K 問題 Kangaroo Puzzle では、ゲームの操作列を構築することが求められました：

パズルは $n$ 行 $m$ 列（$1 \le n, m \le 20$）のグリッドであり、パズル内にはいくつかの（少なくとも $2$ 匹の）カンガルーが立っています。プレイヤーの目標は、彼らを操作して 1 つのマスに集めることです。いくつかのマスには壁があり、カンガルーは壁のあるマスには入れません。他のマスは空きマスです。カンガルーは空きマスから上下左右の 4 方向に隣接する空きマスへ移動できます。

最初、すべての空きマスにちょうど 1 匹のカンガルーがおり、プレイヤーはキーボードのボタン U, D, L, R を押すことでカンガルーを操作できます。カンガルーたちは押されたボタンに従って一斉に移動します。

競技者は目標を達成するために、U, D, L, R のみからなる高々 $5 \times 10^4$ 手の操作列を構築する必要があります。

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 年のコンテストでは 1 問の問題文が 500 ページになってしまうかもしれません。そのため今回は省略します。それに、練習コンテストですでにご覧になっているかもしれません。

さて、2025 年のコンテストでも、皆さんの期待通りカンガルー問題が帰ってきました！なぜ作問者がこれほどカンガルーに執着しているのかは分かりませんが、問題は以下の通りです：

$n$ 行 $m$ 列のグリッドが与えられます。$i_h$ 行目 $j_h$ 列目のマスには穴があります。それ以外のすべてのマスは空きマスであり、各空きマスにはカンガルーが 1 匹ずつ立っています。

同様に、カンガルーはキーボードのボタン U, D, L, R を押すことで操作されます。すべてのカンガルーは押されたボタンに従って一斉に移動します。具体的には、$i$ 行目 $j$ 列目のマス $(i, j)$ にいる任意のカンガルーについて：

1. ボタン U：$(i - 1, j)$ に移動します。
2. ボタン D：$(i + 1, j)$ に移動します。
3. ボタン L：$(i, j - 1)$ に移動します。
4. ボタン R：$(i, j + 1)$ に移動します。

カンガルーが穴の上に移動した（つまり $i = i_h$ かつ $j = j_h$ となった）場合、またはグリッドの外に出た場合、そのカンガルーはグリッドから取り除かれます。

ここで問題となるのは、$i_h$ と $j_h$ の正確な値が分からないことです。あなたの仕事は、高々 $(n + m + 10)$ 回のクエリで穴の位置を特定することです。各クエリでは、ボタン（U, D, L, R のいずれか）を 1 つ押すことができます。ジャッジプログラムは返答として、ボタンを押した後に残っているカンガルーの数を表す整数 $t$ を出力します。

なお、ジャッジプログラムは適応的（adaptive）ではありません。つまり、各テストケースの答えはあらかじめ決定されています。

入力

複数のテストケースが与えられます。入力の 1 行目には、テストケースの個数を表す整数 $T$ ($1 \le T \le 100$) が与えられます。各テストケースについて：

1 行目には、グリッドの行数と列数を表す 2 つの整数 $n$ と $m$ ($3 \le n, m \le 30$) が与えられます。

入出力の方法

クエリを送るには 1 行出力してください。まず ? と空白を 1 つ出力し、続けて英大文字を 1 つ（U, D, L, R のいずれか）出力してください。出力をフラッシュした後、クエリへの返答を表す 1 つの整数 $t$ を読み込んでください。1 つのテストケースにつきクエリは高々 $(n + m + 10)$ 回までしか送れないことに注意してください。

穴の位置を特定できた場合は 1 行出力してください。まず ! と空白を 1 つ出力し、続けて穴の位置を表す 2 つの整数 $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