Đây là bài toán tương tác.

Sau thành công vang dội từ năm 2018 đến năm 2024, Đại học Hàng không Vũ trụ Nam Kinh (NUAA) sẽ đăng cai tổ chức Kỳ thi Lập trình Sinh viên Quốc tế (ICPC) vòng khu vực Nam Kinh lần thứ tám liên tiếp.

Đội Power of Two và đội Three Hold Two đã giành chức vô địch cho Đại học Thanh Hoa vào năm 2018 và 2019. Vào các năm 2020, 2021 và 2022, đội Inverted Cross từ Đại học Bắc Kinh đã giành chức vô địch ba năm liên tiếp, trong khi vào năm 2023, một đội khác là Reborn as a Vegetable Dog từ Đại học Bắc Kinh đã giành ngôi vô địch. Năm 2024, đội Afterlife từ Đại học Chiết Giang đã giành vị trí thứ nhất.

Năm nay, có khoảng $335$ đội tham gia kỳ thi. Tối đa $33$ huy chương vàng, $66$ huy chương bạc và $99$ huy chương đồng sẽ được trao (lưu ý rằng những con số này chỉ mang tính chất tham khảo). Chúng tôi rất mong chờ được chứng kiến màn trình diễn xuất sắc của các thí sinh! Chúng tôi cũng muốn bày tỏ lòng biết ơn đối với sự làm việc chăm chỉ của tất cả các nhân viên và tình nguyện viên cho kỳ thi này. Cảm ơn tất cả các bạn vì những đóng góp to lớn cho kỳ thi!

Bức ảnh được chụp tại Kỳ thi ICPC Khu vực Châu Á - Nam Kinh năm 2023

Trong kỳ thi năm 2018, bài K, Kangaroo Puzzle, yêu cầu các thí sinh xây dựng một dãy thao tác cho trò chơi:

Trò chơi là một lưới gồm $n$ hàng và $m$ cột ($1 \le n, m \le 20$), và có một số (ít nhất là $2$) chú chuột túi đang đứng trong lưới. Mục tiêu của người chơi là điều khiển chúng tụ tập lại cùng một chỗ. Có một số bức tường ở một số ô, và chuột túi không thể đi vào các ô có tường. Các ô còn lại đều trống. Chuột túi có thể di chuyển từ một ô trống sang một ô trống kề cạnh theo bốn hướng: lên, xuống, trái và phải.

Ban đầu có đúng một chú chuột túi ở mỗi ô trống, và người chơi có thể điều khiển các chú chuột túi bằng cách nhấn các nút U, D, L, R trên bàn phím. Các chú chuột túi sẽ di chuyển đồng thời theo nút mà bạn nhấn.

Thí sinh cần xây dựng một dãy thao tác gồm tối đa $5 \times 10^4$ bước chỉ bao gồm U, D, L, R để đạt được mục tiêu.

Trong kỳ thi năm 2020, bài A, Ah, It’s Yesterday Once More, yêu cầu thí sinh xây dựng một bản đồ đầu vào để hack đoạn mã sau của bài toán đã mô tả ở trên:

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

Hơn nữa, trong kỳ thi năm 2021 (Bài A, Oops, It’s Yesterday Twice More), kỳ thi năm 2022 (Bài A, Stop, Yesterday Please No More), kỳ thi năm 2023 (Bài A, Cool, It’s Yesterday Four Times More), và kỳ thi năm 2024 (Bài A, Hey, Have You Seen My Kangaroo?), năm nào chúng ta cũng có một bài toán liên quan đến chuột túi! Chúng tôi rất muốn giới thiệu tất cả những bài toán này cho các bạn, nhưng nếu năm nào cũng làm vậy thì có lẽ đến kỳ thi năm 3025, đề bài của một bài duy nhất sẽ dài tới 500 trang. Vì vậy, lần này chúng tôi xin phép lược bỏ. Ngoài ra, có thể bạn đã thấy chúng trong buổi thi thử rồi.

Giờ đây, trong kỳ thi năm 2025, đúng như mọi người mong đợi, bài toán chuột túi lại quay trở lại! Chúng tôi không biết tại sao những người ra đề lại bị ám ảnh bởi chuột túi đến vậy, nhưng bài toán lần này như sau:

Bạn được cho một lưới gồm $n$ hàng và $m$ cột. Có một cái hố ở ô thuộc hàng thứ $i_h$ và cột thứ $j_h$. Tất cả các ô khác đều trống và có một chú chuột túi đang đứng ở mỗi ô.

Tương tự, các chú chuột túi được điều khiển bằng cách nhấn nút U, D, L, R trên bàn phím. Tất cả chuột túi sẽ di chuyển đồng thời theo nút được nhấn. Cụ thể, đối với bất kỳ chú chuột túi nào nằm ở ô thuộc hàng thứ $i$ và cột thứ $j$, ký hiệu là $(i, j)$:

1. Nút U: nó sẽ di chuyển đến $(i - 1, j)$.
2. Nút D: nó sẽ di chuyển đến $(i + 1, j)$.
3. Nút L: nó sẽ di chuyển đến $(i, j - 1)$.
4. Nút R: nó sẽ di chuyển đến $(i, j + 1)$.

Nếu một chú chuột túi bước vào hố (tức là $i = i_h$ và $j = j_h$) hoặc bước ra ngoài lưới, nó sẽ bị loại khỏi lưới.

Vấn đề là giá trị chính xác của $i_h$ và $j_h$ chưa được biết. Nhiệm vụ của bạn là tìm vị trí của cái hố với tối đa $(n + m + 10)$ truy vấn. Trong mỗi truy vấn, bạn có thể nhấn một nút (U, D, L, hoặc R). Trình tương tác sẽ in ra một số nguyên $t$ làm câu trả lời, cho biết số lượng chuột túi còn lại sau khi bạn nhấn nút.

Lưu ý rằng trình tương tác không thích ứng (non-adaptive), nghĩa là đáp án cho mỗi bộ dữ liệu đã được xác định trước.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của đầu vào chứa một số nguyên $T$ ($1 \le T \le 100$) cho biết số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($3 \le n, m \le 30$) cho biết số hàng và số cột của lưới.

Giao thức tương tác

Để thực hiện một truy vấn, hãy in ra một dòng. Đầu tiên in ra ? theo sau là một dấu cách, sau đó in ra một chữ cái tiếng Anh viết hoa (U, D, L, hoặc R). Sau khi đẩy (flush) dữ liệu đầu ra, chương trình của bạn cần đọc một số nguyên $t$ duy nhất cho biết câu trả lời cho truy vấn của bạn. Hãy nhớ rằng bạn chỉ có thể hỏi tối đa $(n + m + 10)$ truy vấn cho mỗi bộ dữ liệu.

Nếu bạn muốn đoán vị trí của cái hố, hãy in ra một dòng. Đầu tiên in ra ! theo sau là một dấu cách, sau đó in ra hai số nguyên $i_h$ và $j_h$ ($1 \le i_h \le n$, $1 \le j_h \le m$) cách nhau bởi một dấu cách cho biết vị trí. Sau khi flush dữ liệu đầu ra, chương trình của bạn cần tiếp tục xử lý bộ dữ liệu tiếp theo, hoặc thoát ngay lập tức nếu không còn bộ dữ liệu nào nữa. Lưu ý rằng lần đoán của bạn không được tính là một truy vấn.

Để flush dữ liệu đầu ra, bạn có thể sử dụng:

• fflush(stdout) (nếu bạn dùng printf) hoặc cout.flush() (nếu bạn dùng cout) trong C và C++.
• System.out.flush() trong Java và Kotlin.
• sys.stdout.flush() trong Python.

Ví dụ

2
3 4

7

3

4 3

8

5

? L

? D

! 2 3

? U

? R

! 1 1