Dies ist ein interaktives Problem.

Nach dem großen Erfolg von 2018 bis 2024 richtet die Nanjing University of Aeronautics and Astronautics (NUAA) zum achten Mal in Folge den Regionalwettbewerb Nanjing des International Collegiate Programming Contest (ICPC) aus.

Das Team Power of Two und das Team Three Hold Two gewannen 2018 und 2019 den Meistertitel für die Tsinghua-Universität. In den Jahren 2020, 2021 und 2022 gewann das Team Inverted Cross der Peking-Universität dreimal in Folge den Titel, während 2023 ein weiteres Team der Peking-Universität, Reborn as a Vegetable Dog, siegte. Im Jahr 2024 belegte das Team Afterlife der Zhejiang-Universität den ersten Platz.

In diesem Jahr nehmen rund $335$ Teams am Wettbewerb teil. Es werden höchstens $33$ Goldmedaillen, $66$ Silbermedaillen und $99$ Bronzemedaillen vergeben (bitte beachten Sie, dass diese Zahlen nur als Richtwerte dienen). Wir freuen uns auf die herausragenden Leistungen der Teilnehmenden! Außerdem möchten wir allen Mitarbeitenden und Freiwilligen unseren Dank für ihre harte Arbeit bei diesem Wettbewerb aussprechen. Vielen Dank an alle für ihren großartigen Beitrag zu diesem Wettbewerb!

Foto aufgenommen beim 2023 ICPC Asia Nanjing Regional Contest

Im Wettbewerb 2018 verlangte Aufgabe K, Kangaroo Puzzle, von den Teilnehmenden, eine Operationsfolge für das folgende Spiel zu konstruieren:

Das Puzzle ist ein Gitter mit $n$ Zeilen und $m$ Spalten ($1 \le n, m \le 20$), in dem einige (mindestens $2$) Kängurus stehen. Das Ziel des Spielers ist es, sie so zu steuern, dass sie auf einem Feld zusammenkommen. In einigen Feldern befinden sich Wände, und die Kängurus können Felder mit Wänden nicht betreten. Die übrigen Felder sind leer. Die Kängurus können sich von einem leeren Feld auf ein benachbartes leeres Feld in vier Richtungen bewegen: nach oben, unten, links und rechts.

Zu Beginn befindet sich in jedem leeren Feld genau ein Känguru, und der Spieler kann die Kängurus durch Drücken der Tasten U, D, L, R auf der Tastatur steuern. Die Kängurus bewegen sich gleichzeitig entsprechend der gedrückten Taste.

Der Teilnehmende muss eine Operationsfolge von höchstens $5 \times 10^4$ Schritten konstruieren, die nur aus U, D, L, R besteht, um das Ziel zu erreichen.

Im Wettbewerb 2020 verlangte Aufgabe A, Ah, It’s Yesterday Once More, von den Teilnehmenden, eine Eingabekarte zu konstruieren, um den folgenden Code für das zuvor beschriebene Problem zu hacken:

#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;
}

Darüber hinaus gab es im Wettbewerb 2021 (Aufgabe A, Oops, It’s Yesterday Twice More), im Wettbewerb 2022 (Aufgabe A, Stop, Yesterday Please No More), im Wettbewerb 2023 (Aufgabe A, Cool, It’s Yesterday Four Times More) und im Wettbewerb 2024 (Aufgabe A, Hey, Have You Seen My Kangaroo?) jedes Jahr eine Aufgabe rund um Kängurus! Wir würden Ihnen gerne all diese Aufgaben vorstellen, aber wenn wir das jedes Jahr tun, haben wir im Wettbewerb 3025 womöglich eine 500-seitige Aufgabenstellung für eine einzige Aufgabe. Daher lassen wir sie dieses Mal weg. Außerdem haben Sie sie vielleicht schon im Übungswettbewerb gesehen.

Nun, im Wettbewerb 2025, ist die Känguru-Aufgabe – wie von allen erwartet – wieder zurück! Wir wissen nicht, warum die Aufgabensteller so besessen von Kängurus sind, aber die Aufgabe lautet wie folgt:

Gegeben ist ein Gitter mit $n$ Zeilen und $m$ Spalten. Im Feld in der $i_h$-ten Zeile und der $j_h$-ten Spalte befindet sich ein Loch. Alle anderen Felder sind leer, und in jedem dieser Felder steht ein Känguru.

Ebenso werden die Kängurus durch Drücken der Tasten U, D, L, R auf der Tastatur gesteuert. Alle Kängurus bewegen sich gleichzeitig entsprechend der gedrückten Taste. Genauer gesagt gilt für jedes Känguru im Feld in der $i$-ten Zeile und $j$-ten Spalte, bezeichnet mit $(i, j)$:

1. Taste U: es bewegt sich nach $(i - 1, j)$.
2. Taste D: es bewegt sich nach $(i + 1, j)$.
3. Taste L: es bewegt sich nach $(i, j - 1)$.
4. Taste R: es bewegt sich nach $(i, j + 1)$.

Wenn ein Känguru auf das Loch tritt (d. h. $i = i_h$ und $j = j_h$) oder das Gitter verlässt, wird es vom Gitter entfernt.

Das Problem besteht darin, dass die genauen Werte von $i_h$ und $j_h$ unbekannt sind. Ihre Aufgabe ist es, die Position des Lochs mit höchstens $(n + m + 10)$ Anfragen zu bestimmen. Bei jeder Anfrage können Sie eine Taste (U, D, L oder R) drücken. Der Interaktor gibt als Antwort eine ganze Zahl $t$ aus, die angibt, wie viele Kängurus nach dem Tastendruck noch übrig sind.

Beachten Sie, dass der Interaktor nicht adaptiv ist, was bedeutet, dass die Antwort für jeden Testfall im Voraus festgelegt ist.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 100$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:

Die erste Zeile enthält zwei ganze Zahlen $n$ und $m$ ($3 \le n, m \le 30$), die die Anzahl der Zeilen und Spalten im Gitter angeben.

Interaktionsprotokoll

Um eine Anfrage zu stellen, geben Sie eine Zeile aus. Geben Sie zuerst ? gefolgt von einem Leerzeichen aus, und anschließend einen englischen Großbuchstaben (U, D, L oder R). Nach dem Leeren des Ausgabepuffers (Flush) muss Ihr Programm eine einzelne ganze Zahl $t$ einlesen, die die Antwort auf Ihre Anfrage darstellt. Denken Sie daran, dass Sie pro Testfall höchstens $(n + m + 10)$ Anfragen stellen dürfen.

Wenn Sie die Position des Lochs raten möchten, geben Sie eine Zeile aus. Geben Sie zuerst ! gefolgt von einem Leerzeichen aus, und anschließend zwei durch ein Leerzeichen getrennte ganze Zahlen $i_h$ und $j_h$ ($1 \le i_h \le n$, $1 \le j_h \le m$), die die Position angeben. Nach dem Leeren des Ausgabepuffers muss Ihr Programm mit dem nächsten Testfall fortfahren oder sich sofort beenden, falls keine weiteren Testfälle vorliegen. Beachten Sie, dass Ihr Tipp nicht als Anfrage zählt.

Um Ihren Ausgabepuffer zu leeren, können Sie Folgendes verwenden:

• fflush(stdout) (wenn Sie printf verwenden) oder cout.flush() (wenn Sie cout verwenden) in C und C++.
• System.out.flush() in Java und Kotlin.
• sys.stdout.flush() in Python.

Beispiele

2
3 4

7

3

4 3

8

5

? L

? D

! 2 3

? U

? R

! 1 1