Þetta er gagnvirkt verkefni.

Eftir mikla velgengni frá 2018 til 2024 mun Nanjing-flug- og geimferðaháskólinn (NUAA) halda Nanjing-svæðiskeppnina í International Collegiate Programming Contest (ICPC) í áttunda sinn í röð.

Liðið Power of Two og liðið Three Hold Two unnu meistaratitilinn fyrir Tsinghua-háskóla árin 2018 og 2019. Árin 2020, 2021 og 2022 vann liðið Inverted Cross frá Peking-háskóla þrjá meistaratitla í röð, en árið 2023 vann annað lið frá Peking-háskóla, Reborn as a Vegetable Dog, titilinn. Árið 2024 hreppti liðið Afterlife frá Zhejiang-háskóla fyrsta sætið.

Í ár taka um $335$ lið þátt í keppninni. Í mesta lagi verða veitt $33$ gullverðlaun, $66$ silfurverðlaun og $99$ bronsverðlaun (athugið að þessar tölur eru aðeins til viðmiðunar). Við hlökkum til að sjá framúrskarandi frammistöðu keppenda! Við viljum einnig koma á framfæri þakklæti fyrir mikla vinnu allra starfsmanna og sjálfboðaliða við þessa keppni. Takk öll fyrir ykkar mikla framlag til keppninnar!

Mynd tekin í 2023 ICPC Asia Nanjing Regional Contest

Í keppninni árið 2018 krafðist dæmi K, Kangaroo Puzzle, þess að keppendur smíðuðu aðgerðarunu fyrir leikinn:

Þrautin er grind með $n$ röðum og $m$ dálkum ($1 \le n, m \le 20$), og það standa nokkrar (að minnsta kosti $2$) kengúrur í grindinni. Markmið leikmannsins er að stýra þeim þannig að þær safnist saman. Það eru veggir í sumum reitum og kengúrurnar geta ekki farið inn í reiti með veggjum. Hinir reitirnir eru tómir. Kengúrurnar geta færst úr tómum reit yfir í aðliggjandi tóman reit í fjórar áttir: upp, niður, til vinstri og til hægri.

Í upphafi er nákvæmlega ein kengúra í hverjum tómum reit, og leikmaðurinn getur stýrt kengúrunum með því að ýta á hnappana U, D, L, R á lyklaborðinu. Kengúrurnar færast allar samtímis í samræmi við hnappinn sem ýtt er á.

Keppandinn þarf að smíða aðgerðarunu með í mesta lagi $5 \times 10^4$ skrefum sem samanstendur eingöngu af U, D, L, R til að ná markmiðinu.

Í keppninni árið 2020 krafðist dæmi A, Ah, It’s Yesterday Once More, þess að keppendur smíðuðu inntakskort til að hrekkja (hack) eftirfarandi kóða fyrir dæmið sem lýst var hér að ofan:

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

Enn fremur, í keppninni 2021 (Dæmi A, Oops, It’s Yesterday Twice More), keppninni 2022 (Dæmi A, Stop, Yesterday Please No More), keppninni 2023 (Dæmi A, Cool, It’s Yesterday Four Times More) og keppninni 2024 (Dæmi A, Hey, Have You Seen My Kangaroo?), höfum við á hverju ári haft dæmi tengt kengúrum! Okkur langar að kynna öll þessi dæmi fyrir ykkur, en ef við gerum það á hverju ári gætum við endað með 500 blaðsíðna dæmatexta fyrir eitt stakt dæmi í keppninni árið 3025. Þess vegna sleppum við þeim að þessu sinni. Auk þess gætuð þið þegar hafa séð þau í æfingakeppninni.

Nú, í keppninni árið 2025, eins og allir búast við, er kengúrudæmið mætt aftur! Við vitum ekki hvers vegna dæmahöfundar eru svona helteknir af kengúrum, en dæmið er svohljóðandi:

Gefin er grind með $n$ röðum og $m$ dálkum. Það er hola í reitnum í $i_h$-tu röð og $j_h$-ta dálki. Allir aðrir reitir eru tómir og það stendur ein kengúra í hverjum reit.

Á sama hátt er kengúrunum stýrt með því að ýta á hnappana U, D, L, R á lyklaborðinu. Allar kengúrurnar færast samtímis í samræmi við hnappinn sem ýtt var á. Nánar tiltekið, fyrir sérhverja kengúru sem er í reitnum í $i$-tu röð og $j$-ta dálki, táknað með $(i, j)$:

1. Hnappur U: hún færist í $(i - 1, j)$.
2. Hnappur D: hún færist í $(i + 1, j)$.
3. Hnappur L: hún færist í $(i, j - 1)$.
4. Hnappur R: hún færist í $(i, j + 1)$.

Ef kengúra stígur ofan í holuna (það er, $i = i_h$ og $j = j_h$) eða stígur út fyrir grindina, þá er hún fjarlægð af grindinni.

Vandamálið er að nákvæm gildi á $i_h$ og $j_h$ eru ekki þekkt. Verkefni þitt er að finna staðsetningu holunnar með í mesta lagi $(n + m + 10)$ fyrirspurnum. Í hverri fyrirspurn geturðu ýtt á einn hnapp (U, D, L eða R). Gagnvirkniforritið skrifar út heiltölu $t$ sem svar, sem gefur til kynna fjölda kengúra sem eftir eru eftir að þú ýttir á hnappinn.

Athugið að gagnvirkniforritið er ekki aðlögunarhæft (non-adaptive), sem þýðir að svarið fyrir hvert prófunartilvik er ákveðið fyrirfram.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T \le 100$) sem gefur til kynna fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur tvær heiltölur $n$ og $m$ ($3 \le n, m \le 30$) sem gefa til kynna fjölda raða og dálka í grindinni.

Samskiptareglur

Til að spyrja fyrirspurnar skaltu skrifa út eina línu. Skrifaðu fyrst ? og síðan bil, og prentaðu svo einn enskan hástaf (U, D, L eða R). Eftir að hafa tæmt úttaksbiðminnið (flush) ætti forritið þitt að lesa eina heiltölu $t$ sem gefur til kynna svarið við fyrirspurn þinni. Mundu að þú getur spurt í mesta lagi $(n + m + 10)$ fyrirspurna í hverju prófunartilviki.

Ef þú vilt giska á staðsetningu holunnar skaltu skrifa út eina línu. Skrifaðu fyrst ! og síðan bil, og prentaðu svo tvær heiltölur $i_h$ og $j_h$ ($1 \le i_h \le n$, $1 \le j_h \le m$) aðskildar með bili sem gefa til kynna staðsetninguna. Eftir að hafa tæmt úttaksbiðminnið ætti forritið þitt að halda áfram að vinna úr næsta prófunartilviki, eða hætta strax ef engin fleiri prófunartilvik eru eftir. Athugaðu að ágiskunin þín telst ekki sem fyrirspurn.

Til að tæma úttaksbiðminnið geturðu notað:

• fflush(stdout) (ef þú notar printf) eða cout.flush() (ef þú notar cout) í C og C++.
• System.out.flush() í Java og Kotlin.
• sys.stdout.flush() í Python.

Dæmi

2
3 4

7

3

4 3

8

5

? L

? D

! 2 3

? U

? R

! 1 1