Dette er et interaktivt problem.

Etter den store suksessen fra 2018 til 2024 vil Nanjing University of Aeronautics and Astronautics (NUAA) arrangere Nanjing-regionalen i International Collegiate Programming Contest (ICPC) for åttende gang på rad.

Laget Power of Two og laget Three Hold Two vant mestertittelen for Tsinghua-universitetet i 2018 og 2019. I 2020, 2021 og 2022 vant laget Inverted Cross fra Peking-universitetet tre mestertitler på rad, mens et annet lag fra Peking-universitetet, Reborn as a Vegetable Dog, vant tittelen i 2023. I 2024 tok laget Afterlife fra Zhejiang-universitetet førsteplassen.

I år deltar rundt $335$ lag i konkurransen. Det vil bli delt ut maksimalt $33$ gullmedaljer, $66$ sølvmedaljer og $99$ bronsemedaljer (merk at disse tallene kun er veiledende). Vi gleder oss til å se deltakernes fremragende prestasjoner! Vi ønsker også å uttrykke vår takknemlighet for det harde arbeidet som er lagt ned av alle ansatte og frivillige for denne konkurransen. Takk til dere alle for deres store bidrag til konkurransen!

Bilde tatt under 2023 ICPC Asia Nanjing Regional Contest

I konkurransen i 2018 krevde oppgave K, Kangaroo Puzzle, at deltakerne skulle konstruere en operasjonssekvens for spillet:

Puslespillet er et rutenett med $n$ rader og $m$ kolonner ($1 \le n, m \le 20$), og det står noen (minst $2$) kenguruer i rutenettet. Spillerens mål er å styre dem slik at de samles på samme rute. Det er vegger i noen ruter, og kenguruene kan ikke gå inn i rutene med vegger. De andre rutene er tomme. Kenguruene kan bevege seg fra en tom rute til en tilstøtende tom rute i fire retninger: opp, ned, venstre og høyre.

Det står nøyaktig én kenguru i hver tomme rute i starten, og spilleren kan styre kenguruene ved å trykke på knappene U, D, L, R på tastaturet. Kenguruene vil bevege seg samtidig i henhold til knappen du trykker på.

Deltakeren må konstruere en operasjonssekvens på høyst $5 \times 10^4$ steg som kun består av U, D, L, R for å nå målet.

I konkurransen i 2020 krevde oppgave A, Ah, It’s Yesterday Once More, at deltakerne skulle konstruere et inndatakart for å hacke følgende kode for problemet beskrevet ovenfor:

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

Videre, i konkurransen i 2021 (Oppgave A, Oops, It’s Yesterday Twice More), konkurransen i 2022 (Oppgave A, Stop, Yesterday Please No More), konkurransen i 2023 (Oppgave A, Cool, It’s Yesterday Four Times More) og konkurransen i 2024 (Oppgave A, Hey, Have You Seen My Kangaroo?), har vi hvert eneste år hatt en oppgave relatert til kenguruer! Vi skulle gjerne ha presentert alle disse oppgavene for dere, men hvis vi gjør det hvert år, ender vi kanskje opp med en oppgavetekst på 500 sider for én enkelt oppgave i konkurransen i 3025. Derfor utelater vi dem denne gangen. Dessuten har du kanskje allerede sett dem i treningskonkurransen.

Nå, i konkurransen i 2025, som alle forventer, er kenguruoppgaven tilbake igjen! Vi vet ikke hvorfor oppgaveforfatterne er så opphengt i kenguruer, men oppgaven er som følger:

Du får et rutenett med $n$ rader og $m$ kolonner. Det er et hull i ruten på den $i_h$-te raden og den $j_h$-te kolonnen. Alle andre ruter er tomme, og det står én kenguru i hver rute.

På samme måte styres kenguruene ved å trykke på knappen U, D, L, R på tastaturet. Alle kenguruene vil bevege seg samtidig i henhold til knappen som trykkes. Mer spesifikt, for enhver kenguru som befinner seg i ruten på den $i$-te raden og den $j$-te kolonnen, angitt ved $(i, j)$:

1. Knapp U: den flytter seg til $(i - 1, j)$.
2. Knapp D: den flytter seg til $(i + 1, j)$.
3. Knapp L: den flytter seg til $(i, j - 1)$.
4. Knapp R: den flytter seg til $(i, j + 1)$.

Hvis en kenguru tråkker ned i hullet (det vil si $i = i_h$ og $j = j_h$) eller går utenfor rutenettet, blir den fjernet fra rutenettet.

Problemet er at de eksakte verdiene til $i_h$ og $j_h$ ikke er kjent. Din oppgave er å finne posisjonen til hullet med høyst $(n + m + 10)$ spørringer. For hver spørring kan du trykke på én knapp (U, D, L eller R). Interaktoren vil skrive ut et heltall $t$ som svar, som angir antallet kenguruer som er igjen etter at du har trykket på knappen.

Merk at interaktoren ikke er adaptiv, noe som betyr at svaret for hvert testtilfelle er fastsatt på forhånd.

Inndata

Det er flere testtilfeller. Den første linjen av inndataen inneholder et heltall $T$ ($1 \le T \le 100$) som angir antallet testtilfeller. For hvert testtilfelle:

Den første linjen inneholder to heltall $n$ og $m$ ($3 \le n, m \le 30$) som angir antallet rader og kolonner i rutenettet.

Interaksjonsprotokoll

For å stille en spørring, skriv ut én linje. Skriv først ut ? etterfulgt av et mellomrom, og skriv deretter ut én stor engelsk bokstav (U, D, L eller R). Etter å ha tømt utdatabufferen (flush), må programmet ditt lese ett enkelt heltall $t$ som angir svaret på spørringen din. Husk at du kan stille høyst $(n + m + 10)$ spørringer for hvert testtilfelle.

Hvis du vil gjette posisjonen til hullet, skriv ut én linje. Skriv først ut ! etterfulgt av et mellomrom, og skriv deretter ut to heltall $i_h$ og $j_h$ ($1 \le i_h \le n$, $1 \le j_h \le m$) atskilt med et mellomrom som angir posisjonen. Etter å ha tømt utdatabufferen, må programmet ditt fortsette med neste testtilfelle, eller avslutte umiddelbart hvis det ikke er flere testtilfeller. Merk at gjetningen din ikke teller som en spørring.

For å tømme utdatabufferen kan du bruke:

• fflush(stdout) (hvis du bruker printf) eller cout.flush() (hvis du bruker cout) i C og C++.
• System.out.flush() i Java og Kotlin.
• sys.stdout.flush() i Python.

Eksempler

2
3 4

7

3

4 3

8

5

? L

? D

! 2 3

? U

? R

! 1 1