Detta är ett interaktivt problem.

Efter de stora framgångarna från 2018 till 2024 kommer Nanjing University of Aeronautics and Astronautics (NUAA) att stå värd för regiontävlingen i Nanjing i International Collegiate Programming Contest (ICPC) för åttonde gången i rad.

Laget Power of Two och laget Three Hold Two vann mästartiteln för Tsinghua-universitetet 2018 och 2019. Åren 2020, 2021 och 2022 tog laget Inverted Cross från Pekinguniversitetet tre raka mästartitlar, medan ett annat lag från Pekinguniversitetet, Reborn as a Vegetable Dog, vann titeln 2023. År 2024 tog laget Afterlife från Zhejiang-universitetet första platsen.

I år deltar omkring $335$ lag i tävlingen. Högst $33$ guldmedaljer, $66$ silvermedaljer och $99$ bronsmedaljer kommer att delas ut (observera att dessa siffror endast är riktvärden). Vi ser fram emot att få se deltagarnas enastående prestationer! Vi vill också rikta ett varmt tack till all personal och alla volontärer för deras hårda arbete med denna tävling. Tack alla för er fantastiska insats i tävlingen!

Foto taget under 2023 ICPC Asia Nanjing Regional Contest

I tävlingen 2018 krävde problem K, Kangaroo Puzzle, att de tävlande skulle konstruera en operationsföljd för spelet:

Pusslet är ett rutnät med $n$ rader och $m$ kolumner ($1 \le n, m \le 20$), och det står några (minst $2$) kängurur i pusslet. Spelarens mål är att styra dem så att de samlas på samma ruta. Det finns väggar i vissa rutor, och kängururna kan inte gå in i rutor med väggar. De övriga rutorna är tomma. Kängururna kan förflytta sig från en tom ruta till en intilliggande tom ruta i fyra riktningar: upp, ner, vänster och höger.

Det står exakt en känguru i varje tom ruta från början, och spelaren kan styra kängururna genom att trycka på knapparna U, D, L, R på tangentbordet. Kängururna flyttar sig samtidigt enligt knappen du trycker på.

Den tävlande behöver konstruera en operationsföljd med högst $5 \times 10^4$ steg som endast består av U, D, L, R för att uppnå målet.

I tävlingen 2020 krävde problem A, Ah, It’s Yesterday Once More, att de tävlande skulle konstruera en indatakarta för att hacka följande kod för problemet som beskrevs ovan:

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

Dessutom har vi i tävlingen 2021 (Problem A, Oops, It’s Yesterday Twice More), tävlingen 2022 (Problem A, Stop, Yesterday Please No More), tävlingen 2023 (Problem A, Cool, It’s Yesterday Four Times More) och tävlingen 2024 (Problem A, Hey, Have You Seen My Kangaroo?) varje år haft ett problem relaterat till kängurur! Vi skulle gärna presentera alla dessa problem för er, men om vi gör det varje år kanske vi får en problemtext på 500 sidor för ett enda problem i tävlingen år 3025. Därför utelämnar vi dem den här gången. Dessutom har ni kanske redan sett dem i övningstävlingen.

Nu, i tävlingen 2025, är känguruproblemet som alla förväntat sig tillbaka igen! Vi vet inte varför problemskaparna är så besatta av kängurur, men problemet lyder som följer:

Du får ett rutnät med $n$ rader och $m$ kolumner. Det finns ett hål i rutan på den $i_h$-te raden och den $j_h$-te kolumnen. Alla andra rutor är tomma och det står en känguru i varje sådan ruta.

På samma sätt styrs kängururna genom att trycka på knappen U, D, L, R på tangentbordet. Alla kängurur flyttar sig samtidigt enligt den nedtryckta knappen. Mer specifikt, för varje känguru som befinner sig i rutan på den $i$-te raden och den $j$-te kolumnen, betecknad med $(i, j)$:

1. Knapp U: den flyttar sig till $(i - 1, j)$.
2. Knapp D: den flyttar sig till $(i + 1, j)$.
3. Knapp L: den flyttar sig till $(i, j - 1)$.
4. Knapp R: den flyttar sig till $(i, j + 1)$.

Om en känguru kliver ner i hålet (det vill säga $i = i_h$ och $j = j_h$) eller kliver utanför rutnätet, tas den bort från rutnätet.

Problemet är att de exakta värdena på $i_h$ och $j_h$ inte är kända. Din uppgift är att hitta hålets position med högst $(n + m + 10)$ frågor. För varje fråga kan du trycka på en knapp (U, D, L eller R). Interaktorn skriver ut ett heltal $t$ som svar, vilket anger antalet kängurur som finns kvar efter att du tryckt på knappen.

Observera att interaktorn inte är adaptiv, vilket innebär att svaret för varje testfall är bestämt på förhand.

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett heltal $T$ ($1 \le T \le 100$) som anger antalet testfall. För varje testfall:

Den första raden innehåller två heltal $n$ och $m$ ($3 \le n, m \le 30$) som anger antalet rader och kolumner i rutnätet.

Interaktionsprotokoll

För att ställa en fråga, skriv ut en rad. Skriv först ut ? följt av ett mellanslag, och skriv sedan ut en versal engelsk bokstav (U, D, L eller R). Efter att du tömt utdatabufferten (flush) ska ditt program läsa in ett enda heltal $t$ som anger svaret på din fråga. Kom ihåg att du kan ställa högst $(n + m + 10)$ frågor per testfall.

Om du vill gissa hålets position, skriv ut en rad. Skriv först ut ! följt av ett mellanslag, och skriv sedan ut två heltal $i_h$ och $j_h$ ($1 \le i_h \le n$, $1 \le j_h \le m$) åtskilda av ett mellanslag som anger positionen. Efter att du tömt utdatabufferten ska ditt program fortsätta att bearbeta nästa testfall, eller avslutas omedelbart om det inte finns fler testfall. Observera att din gissning inte räknas som en fråga.

För att tömma utdatabufferten kan du använda:

• fflush(stdout) (om du använder printf) eller cout.flush() (om du använder cout) i C och C++.
• System.out.flush() i Java och Kotlin.
• sys.stdout.flush() i Python.

Exempel

2
3 4

7

3

4 3

8

5

? L

? D

! 2 3

? U

? R

! 1 1