To jest zadanie interaktywne.

Po wielkim sukcesie w latach 2018–2024 Uniwersytet Aeronautyki i Astronautyki w Nankinie (NUAA) po raz ósmy z rzędu będzie gospodarzem zawodów regionalnych International Collegiate Programming Contest (ICPC) w Nankinie.

Drużyny Power of Two oraz Three Hold Two zdobyły tytuły mistrzowskie dla Uniwersytetu Tsinghua w latach 2018 i 2019. W latach 2020, 2021 i 2022 drużyna Inverted Cross z Uniwersytetu Pekińskiego zdobyła tytuł mistrzowski trzy razy z rzędu, natomiast w 2023 roku zwyciężyła inna drużyna z Uniwersytetu Pekińskiego — Reborn as a Vegetable Dog. W 2024 roku pierwsze miejsce zajęła drużyna Afterlife z Uniwersytetu Zhejiang.

W tym roku w zawodach bierze udział około $335$ drużyn. Przyznanych zostanie co najwyżej $33$ złotych medali, $66$ srebrnych medali oraz $99$ brązowych medali (uwaga: liczby te mają wyłącznie charakter orientacyjny). Z niecierpliwością czekamy na znakomite występy uczestników! Chcemy również wyrazić wdzięczność za ciężką pracę wykonaną przez wszystkich pracowników i wolontariuszy przy organizacji tych zawodów. Dziękujemy wam wszystkim za ogromny wkład w ten konkurs!

Zdjęcie wykonane podczas zawodów 2023 ICPC Asia Nanjing Regional Contest

W zawodach z 2018 roku zadanie K, Kangaroo Puzzle, wymagało od uczestników skonstruowania ciągu operacji dla następującej gry:

Łamigłówka jest siatką o $n$ wierszach i $m$ kolumnach ($1 \le n, m \le 20$), w której znajduje się pewna liczba (co najmniej $2$) kangurów. Celem gracza jest pokierowanie nimi tak, aby zebrały się w jednym miejscu. W niektórych polach znajdują się ściany i kangury nie mogą wchodzić na pola ze ścianami. Pozostałe pola są puste. Kangury mogą przemieszczać się z pustego pola na sąsiednie puste pole w czterech kierunkach: w górę, w dół, w lewo i w prawo.

Na początku na każdym pustym polu stoi dokładnie jeden kangur, a gracz może sterować kangurami, naciskając klawisze U, D, L, R na klawiaturze. Kangury poruszają się jednocześnie zgodnie z naciśniętym klawiszem.

Uczestnik musi skonstruować ciąg operacji składający się z co najwyżej $5 \times 10^4$ kroków, zawierający wyłącznie znaki U, D, L, R, aby osiągnąć cel.

W zawodach z 2020 roku zadanie A, Ah, It’s Yesterday Once More, wymagało od uczestników skonstruowania mapy wejściowej hakującej poniższy kod do opisanego wcześniej zadania:

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

Co więcej, w zawodach z 2021 roku (Zadanie A, Oops, It’s Yesterday Twice More), w zawodach z 2022 roku (Zadanie A, Stop, Yesterday Please No More), w zawodach z 2023 roku (Zadanie A, Cool, It’s Yesterday Four Times More) oraz w zawodach z 2024 roku (Zadanie A, Hey, Have You Seen My Kangaroo?) co roku pojawiało się zadanie związane z kangurami! Chcielibyśmy przedstawić wam wszystkie te zadania, ale gdybyśmy robili to co roku, w zawodach w 3025 roku treść jednego zadania mogłaby liczyć 500 stron. Dlatego tym razem je pomijamy. Poza tym być może widzieliście je już podczas sesji próbnej.

Teraz, w zawodach z 2025 roku, zgodnie z oczekiwaniami wszystkich, zadanie o kangurach powraca! Nie wiemy, dlaczego autorzy zadań mają taką obsesję na punkcie kangurów, ale treść zadania jest następująca:

Dana jest siatka o $n$ wierszach i $m$ kolumnach. W polu w $i_h$-tym wierszu i $j_h$-tej kolumnie znajduje się dziura. Wszystkie pozostałe pola są puste i na każdym z nich stoi jeden kangur.

Podobnie jak wcześniej, kangurami steruje się poprzez naciskanie klawiszy U, D, L, R na klawiaturze. Wszystkie kangury poruszają się jednocześnie zgodnie z naciśniętym klawiszem. Dokładniej, dla każdego kangura znajdującego się na polu w $i$-tym wierszu i $j$-tej kolumnie, oznaczanym przez $(i, j)$:

1. Klawisz U: kangur przemieści się na pole $(i - 1, j)$.
2. Klawisz D: kangur przemieści się na pole $(i + 1, j)$.
3. Klawisz L: kangur przemieści się na pole $(i, j - 1)$.
4. Klawisz R: kangur przemieści się na pole $(i, j + 1)$.

Jeśli kangur wejdzie do dziury (to znaczy $i = i_h$ oraz $j = j_h$) lub wyjdzie poza siatkę, zostaje usunięty z siatki.

Problem polega na tym, że dokładne wartości $i_h$ oraz $j_h$ nie są znane. Twoim zadaniem jest znalezienie pozycji dziury przy użyciu co najwyżej $(n + m + 10)$ zapytań. W każdym zapytaniu możesz nacisnąć jeden klawisz (U, D, L lub R). Interaktor wypisze w odpowiedzi liczbę całkowitą $t$, oznaczającą liczbę kangurów pozostałych na siatce po naciśnięciu klawisza.

Zauważ, że interaktor nie jest adaptacyjny, co oznacza, że odpowiedź dla każdego przypadku testowego jest ustalona z góry.

Wejście

Dane wejściowe składają się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 100$) oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $m$ ($3 \le n, m \le 30$) oznaczające liczbę wierszy i kolumn siatki.

Protokół interakcji

Aby zadać zapytanie, wypisz jeden wiersz. Najpierw wypisz znak ?, następnie spację, a potem jedną wielką literę alfabetu angielskiego (U, D, L lub R). Po opróżnieniu bufora wyjścia (flush) Twój program powinien wczytać jedną liczbę całkowitą $t$, oznaczającą odpowiedź na Twoje zapytanie. Pamiętaj, że możesz zadać co najwyżej $(n + m + 10)$ zapytań w jednym przypadku testowym.

Jeśli chcesz odgadnąć pozycję dziury, wypisz jeden wiersz. Najpierw wypisz znak !, następnie spację, a potem dwie liczby całkowite $i_h$ oraz $j_h$ ($1 \le i_h \le n$, $1 \le j_h \le m$) oddzielone spacją, oznaczające pozycję dziury. Po opróżnieniu bufora wyjścia Twój program powinien przejść do przetwarzania kolejnego przypadku testowego lub natychmiast zakończyć działanie, jeśli nie ma więcej przypadków testowych. Zauważ, że podanie odpowiedzi nie wlicza się do limitu zapytań.

Aby opróżnić bufor wyjścia, możesz użyć:

• fflush(stdout) (jeśli używasz printf) lub cout.flush() (jeśli używasz cout) w C i C++.
• System.out.flush() w Javie i Kotlinie.
• sys.stdout.flush() w Pythonie.

Przykład

2
3 4

7

3

4 3

8

5

? L

? D

! 2 3

? U

? R

! 1 1