Tämä on vuorovaikutteinen tehtävä.

Vuosien 2018–2024 suuren menestyksen jälkeen Nanjingin ilmailu- ja avaruusyliopisto (NUAA) järjestää International Collegiate Programming Contest (ICPC) -kilpailun Nanjingin aluekilpailun kahdeksannen kerran peräkkäin.

Joukkueet Power of Two ja Three Hold Two voittivat mestaruuden Tsinghuan yliopistolle vuosina 2018 ja 2019. Vuosina 2020, 2021 ja 2022 Pekingin yliopiston joukkue Inverted Cross voitti kolme peräkkäistä mestaruutta, kun taas vuonna 2023 mestaruuden voitti toinen Pekingin yliopiston joukkue Reborn as a Vegetable Dog. Vuonna 2024 ensimmäisen sijan vei Zhejiangin yliopiston joukkue Afterlife.

Tänä vuonna kilpailuun osallistuu noin $335$ joukkuetta. Kilpailussa jaetaan enintään $33$ kultamitalia, $66$ hopeamitalia ja $99$ pronssimitalia (huomaa, että nämä luvut ovat vain viitteellisiä). Odotamme innolla osallistujien huippusuorituksia! Haluamme myös esittää kiitoksemme kaikille työntekijöille ja vapaaehtoisille heidän kovasta työstään tämän kilpailun eteen. Kiitos teille kaikille suuresta panoksestanne tämän kilpailun hyväksi!

Kuva otettu vuoden 2023 ICPC Asia Nanjing Regional Contest -kilpailussa

Vuoden 2018 kilpailussa tehtävä K, Kangaroo Puzzle, vaati kilpailijoita muodostamaan toimintosarjan seuraavaan peliin:

Pelilauta on ruudukko, jossa on $n$ riviä ja $m$ saraketta ($1 \le n, m \le 20$), ja ruudukossa seisoo joitakin (vähintään $2$) kenguruita. Pelaajan tavoitteena on ohjata ne kokoontumaan yhteen. Joissakin ruuduissa on seiniä, eivätkä kengurut voi mennä seinällisiin ruutuihin. Muut ruudut ovat tyhjiä. Kengurut voivat liikkua tyhjästä ruudusta viereiseen tyhjään ruutuun neljässä suunnassa: ylös, alas, vasemmalle ja oikealle.

Alussa jokaisessa tyhjässä ruudussa on täsmälleen yksi kenguru, ja pelaaja voi ohjata kenguruita painamalla näppäimistön painikkeita U, D, L, R. Kengurut liikkuvat samanaikaisesti painamasi painikkeen mukaisesti.

Kilpailijan tulee muodostaa enintään $5 \times 10^4$ askeleesta koostuva pelkästään merkeistä U, D, L, R muodostuva toimintosarja tavoitteen saavuttamiseksi.

Vuoden 2020 kilpailussa tehtävä A, Ah, It’s Yesterday Once More, vaati kilpailijoita muodostamaan syötekartan, joka murtaa (hack) edellä kuvatun tehtävän seuraavan koodin:

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

Lisäksi vuoden 2021 kilpailussa (Tehtävä A, Oops, It’s Yesterday Twice More), vuoden 2022 kilpailussa (Tehtävä A, Stop, Yesterday Please No More), vuoden 2023 kilpailussa (Tehtävä A, Cool, It’s Yesterday Four Times More) ja vuoden 2024 kilpailussa (Tehtävä A, Hey, Have You Seen My Kangaroo?) meillä on joka vuosi ollut kenguruihin liittyvä tehtävä! Haluaisimme esitellä teille kaikki nämä tehtävät, mutta jos teemme niin joka vuosi, vuoden 3025 kilpailussa yhden ainoan tehtävän tehtävänanto saattaa olla 500 sivun mittainen. Siksi jätämme ne tällä kertaa pois. Sitä paitsi olette saattaneet jo nähdä ne harjoituskilpailussa.

Nyt vuoden 2025 kilpailussa, aivan kuten kaikki odottavatkin, kengurutehtävä on taas täällä! Emme tiedä, miksi tehtävänlaatijat ovat niin pakkomielteisen kiinnostuneita kenguruista, mutta tehtävä kuuluu seuraavasti:

Sinulle annetaan ruudukko, jossa on $n$ riviä ja $m$ saraketta. Rivin $i_h$ ja sarakkeen $j_h$ ruudussa on kuoppa. Kaikki muut ruudut ovat tyhjiä, ja jokaisessa niistä seisoo yksi kenguru.

Aivan kuten aiemminkin, kenguruita ohjataan painamalla näppäimistön painikkeita U, D, L, R. Kaikki kengurut liikkuvat samanaikaisesti painetun painikkeen mukaisesti. Tarkemmin sanottuna mille tahansa rivin $i$ ja sarakkeen $j$ ruudussa $(i, j)$ olevalle kengurulle:

1. Painike U: se siirtyy ruutuun $(i - 1, j)$.
2. Painike D: se siirtyy ruutuun $(i + 1, j)$.
3. Painike L: se siirtyy ruutuun $(i, j - 1)$.
4. Painike R: se siirtyy ruutuun $(i, j + 1)$.

Jos kenguru astuu kuoppaan (eli $i = i_h$ ja $j = j_h$) tai astuu ulos ruudukosta, se poistetaan ruudukosta.

Ongelmana on, että lukujen $i_h$ ja $j_h$ tarkkoja arvoja ei tiedetä. Tehtäväsi on selvittää kuopan sijainti enintään $(n + m + 10)$ kyselyllä. Jokaisella kyselyllä voit painaa yhtä painiketta (U, D, L tai R). Vuorovaikutusohjelma tulostaa vastauksena kokonaisluvun $t$, joka ilmaisee painikkeen painamisen jälkeen jäljellä olevien kenguruiden lukumäärän.

Huomaa, että vuorovaikutusohjelma ei ole mukautuva (non-adaptive), mikä tarkoittaa, että kunkin testitapauksen vastaus on päätetty etukäteen.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 100$), joka ilmaisee testitapausten lukumäärän. Jokaisessa testitapauksessa:

Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($3 \le n, m \le 30$), jotka ilmaisevat ruudukon rivien ja sarakkeiden lukumäärän.

Vuorovaikutusprotokolla

Tehdäksesi kyselyn tulosta yksi rivi. Tulosta ensin ? ja välilyönti, ja tulosta sen jälkeen yksi iso englantilainen kirjain (U, D, L tai R). Tulostepuskurin tyhjentämisen (flush) jälkeen ohjelmasi tulee lukea yksi kokonaisluku $t$, joka ilmaisee vastauksen kyselyysi. Muista, että voit tehdä enintään $(n + m + 10)$ kyselyä yhtä testitapausta kohden.

Jos haluat arvata kuopan sijainnin, tulosta yksi rivi. Tulosta ensin ! ja välilyönti, ja tulosta sen jälkeen kaksi välilyönnillä erotettua kokonaislukua $i_h$ ja $j_h$ ($1 \le i_h \le n$, $1 \le j_h \le m$), jotka ilmaisevat sijainnin. Tulostepuskurin tyhjentämisen jälkeen ohjelmasi tulee jatkaa seuraavan testitapauksen käsittelyä tai lopettaa välittömästi, jos testitapauksia ei ole enää jäljellä. Huomaa, että arvaustasi ei lasketa kyselyksi.

Tulostepuskurin tyhjentämiseen voit käyttää:

• fflush(stdout) (jos käytät printf-funktiota) tai cout.flush() (jos käytät cout-virtaa) C:ssä ja C++:ssa.
• System.out.flush() Javassa ja Kotlinissa.
• sys.stdout.flush() Pythonissa.

Esimerkit

2
3 4

7

3

4 3

8

5

? L

? D

! 2 3

? U

? R

! 1 1