Ini adalah soal interaktif.

Setelah kesuksesan besar dari tahun 2018 hingga 2024, Nanjing University of Aeronautics and Astronautics (NUAA) akan menjadi tuan rumah regional Nanjing International Collegiate Programming Contest (ICPC) untuk kedelapan kalinya secara berturut-turut.

Tim Power of Two dan tim Three Hold Two memenangkan gelar juara untuk Tsinghua University pada tahun 2018 dan 2019. Pada tahun 2020, 2021, dan 2022, tim Inverted Cross dari Peking University memenangkan gelar juara tiga kali berturut-turut, sementara pada tahun 2023, tim lain Reborn as a Vegetable Dog dari Peking University memenangkan gelar tersebut. Pada tahun 2024, tim Afterlife dari Zhejiang University meraih peringkat pertama.

Tahun ini, sekitar $335$ tim berpartisipasi dalam kontes ini. Paling banyak $33$ medali emas, $66$ medali perak, dan $99$ medali perunggu akan diberikan (perhatikan bahwa angka-angka ini hanya sebagai referensi). Kami sangat menantikan penampilan luar biasa dari para peserta! Kami juga ingin menyampaikan rasa terima kasih atas kerja keras yang dilakukan oleh seluruh staf dan sukarelawan untuk kontes ini. Terima kasih semuanya atas kontribusi besar kalian untuk kontes ini!

Foto diambil pada 2023 ICPC Asia Nanjing Regional Contest

Pada kontes tahun 2018, soal K, Kangaroo Puzzle, meminta para peserta untuk menyusun barisan operasi untuk permainan berikut:

Teka-teki ini adalah sebuah grid dengan $n$ baris dan $m$ kolom ($1 \le n, m \le 20$), dan terdapat beberapa (setidaknya $2$) kanguru yang berdiri di dalam teka-teki tersebut. Tujuan pemain adalah mengendalikan mereka agar berkumpul bersama. Terdapat dinding di beberapa sel, dan kanguru tidak dapat memasuki sel yang memiliki dinding. Sel-sel lainnya kosong. Kanguru dapat bergerak dari sel kosong ke sel kosong yang bersebelahan dalam empat arah: atas, bawah, kiri, dan kanan.

Terdapat tepat satu kanguru di setiap sel kosong pada awalnya, dan pemain dapat mengendalikan kanguru dengan menekan tombol U, D, L, R pada papan ketik. Kanguru-kanguru tersebut akan bergerak secara bersamaan sesuai dengan tombol yang Anda tekan.

Peserta harus menyusun barisan operasi paling banyak $5 \times 10^4$ langkah yang hanya terdiri dari U, D, L, R untuk mencapai tujuan tersebut.

Pada kontes tahun 2020, soal A, Ah, It’s Yesterday Once More, meminta peserta untuk menyusun peta masukan guna meng-hack kode berikut dari soal yang dijelaskan sebelumnya:

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

Lebih lanjut, pada kontes tahun 2021 (Soal A, Oops, It’s Yesterday Twice More), kontes tahun 2022 (Soal A, Stop, Yesterday Please No More), kontes tahun 2023 (Soal A, Cool, It’s Yesterday Four Times More), dan kontes tahun 2024 (Soal A, Hey, Have You Seen My Kangaroo?), setiap tahun kita memiliki soal yang berkaitan dengan kanguru! Kami ingin memperkenalkan semua soal ini kepada Anda, tetapi jika kami melakukannya setiap tahun, kita mungkin akan memiliki deskripsi soal sepanjang 500 halaman untuk satu soal saja pada kontes tahun 3025. Oleh karena itu, kami melewatkannya kali ini. Selain itu, Anda mungkin sudah melihatnya di kontes latihan.

Sekarang, pada kontes tahun 2025, seperti yang diharapkan semua orang, soal kanguru kembali lagi! Kami tidak tahu mengapa pembuat soal begitu terobsesi dengan kanguru, tetapi soalnya adalah sebagai berikut:

Anda diberikan sebuah grid dengan $n$ baris dan $m$ kolom. Terdapat sebuah lubang di sel pada baris ke-$i_h$ dan kolom ke-$j_h$. Semua sel lainnya kosong dan terdapat satu kanguru yang berdiri di setiap sel.

Serupa dengan sebelumnya, kanguru-kanguru tersebut dikendalikan dengan menekan tombol U, D, L, R pada papan ketik. Semua kanguru akan bergerak secara bersamaan sesuai dengan tombol yang ditekan. Secara spesifik, untuk setiap kanguru yang berada di sel pada baris ke-$i$ dan kolom ke-$j$, yang dinyatakan dengan $(i, j)$:

1. Tombol U: ia akan bergerak ke $(i - 1, j)$.
2. Tombol D: ia akan bergerak ke $(i + 1, j)$.
3. Tombol L: ia akan bergerak ke $(i, j - 1)$.
4. Tombol R: ia akan bergerak ke $(i, j + 1)$.

Jika seekor kanguru melangkah ke lubang (yaitu, $i = i_h$ dan $j = j_h$) atau melangkah keluar dari grid, ia akan dihapus dari grid.

Masalahnya adalah nilai pasti dari $i_h$ dan $j_h$ tidak diketahui. Tugas Anda adalah menemukan posisi lubang tersebut dengan paling banyak $(n + m + 10)$ kueri. Untuk setiap kueri, Anda dapat menekan satu tombol (U, D, L, atau R). Interaktor akan mengeluarkan sebuah bilangan bulat $t$ sebagai jawaban, yang menyatakan jumlah kanguru yang tersisa setelah Anda menekan tombol tersebut.

Perhatikan bahwa interaktor tidak adaptif, yang berarti jawaban untuk setiap kasus uji sudah ditentukan sebelumnya.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 100$) yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama berisi dua bilangan bulat $n$ dan $m$ ($3 \le n, m \le 30$) yang menyatakan jumlah baris dan kolom pada grid.

Protokol Interaksi

Untuk mengajukan kueri, keluarkan satu baris. Pertama keluarkan ? diikuti oleh sebuah spasi, lalu cetak satu huruf bahasa Inggris kapital (U, D, L, atau R). Setelah melakukan flush pada keluaran Anda, program Anda harus membaca sebuah bilangan bulat $t$ yang menyatakan jawaban atas kueri Anda. Ingat bahwa Anda dapat mengajukan paling banyak $(n + m + 10)$ kueri untuk satu kasus uji.

Jika Anda ingin menebak posisi lubang, keluarkan satu baris. Pertama keluarkan ! diikuti oleh sebuah spasi, lalu cetak dua bilangan bulat $i_h$ dan $j_h$ ($1 \le i_h \le n$, $1 \le j_h \le m$) yang dipisahkan oleh sebuah spasi yang menyatakan posisi tersebut. Setelah melakukan flush pada keluaran Anda, program Anda harus melanjutkan pemrosesan kasus uji berikutnya, atau segera keluar jika tidak ada kasus uji lagi. Perhatikan bahwa tebakan Anda tidak dihitung sebagai kueri.

Untuk melakukan flush pada keluaran Anda, Anda dapat menggunakan:

• fflush(stdout) (jika Anda menggunakan printf) atau cout.flush() (jika Anda menggunakan cout) di C dan C++.
• System.out.flush() di Java dan Kotlin.
• sys.stdout.flush() di Python.

Contoh

2
3 4

7

3

4 3

8

5

? L

? D

! 2 3

? U

? R

! 1 1