Це інтерактивна задача.

Після величезного успіху з 2018 по 2024 рік Нанкінський університет аеронавтики та астронавтики (NUAA) увосьме поспіль прийматиме регіональний етап Міжнародної студентської олімпіади з програмування (ICPC) у Нанкіні.

Команди Power of Two та Three Hold Two вибороли чемпіонські титули для Університету Цінхуа у 2018 та 2019 роках. У 2020, 2021 та 2022 роках команда Inverted Cross із Пекінського університету тричі поспіль здобувала титул чемпіона, а в 2023 році чемпіонський титул виборола інша команда з Пекінського університету — Reborn as a Vegetable Dog. У 2024 році перше місце посіла команда Afterlife з Чжецзянського університету.

Цього року в змаганні беруть участь близько $335$ команд. Буде вручено щонайбільше $33$ золоті медалі, $66$ срібних медалей та $99$ бронзових медалей (зверніть увагу, що ці числа наведено лише для довідки). Ми з нетерпінням чекаємо на видатні виступи учасників! Ми також хочемо висловити нашу вдячність усім співробітникам та волонтерам за їхню наполегливу працю під час підготовки цього змагання. Дякуємо всім вам за ваш вагомий внесок у це змагання!

Фотографію зроблено на 2023 ICPC Asia Nanjing Regional Contest

У змаганні 2018 року задача K, Kangaroo Puzzle, вимагала від учасників побудувати послідовність операцій для такої гри:

Головоломка — це сітка з $n$ рядків та $m$ стовпців ($1 \le n, m \le 20$), у якій стоять декілька (щонайменше $2$) кенгуру. Мета гравця — керувати ними так, щоб зібрати їх разом. У деяких клітинках є стіни, і кенгуру не можуть заходити в клітинки зі стінами. Інші клітинки порожні. Кенгуру можуть переміщуватися з порожньої клітинки до сусідньої порожньої клітинки в чотирьох напрямках: вгору, вниз, вліво та вправо.

Спочатку в кожній порожній клітинці стоїть рівно один кенгуру, і гравець може керувати кенгуру, натискаючи кнопки U, D, L, R на клавіатурі. Кенгуру рухатимуться одночасно відповідно до натиснутої кнопки.

Учаснику потрібно побудувати послідовність операцій із щонайбільше $5 \times 10^4$ кроків, яка складається лише з U, D, L, R, щоб досягти мети.

У змаганні 2020 року задача A, Ah, It’s Yesterday Once More, вимагала від учасників побудувати вхідну карту, щоб зламати (хакнути) наведений нижче код описаної раніше задачі:

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

Крім того, у змаганні 2021 року (задача A, Oops, It’s Yesterday Twice More), змаганні 2022 року (задача A, Stop, Yesterday Please No More), змаганні 2023 року (задача A, Cool, It’s Yesterday Four Times More) та змаганні 2024 року (задача A, Hey, Have You Seen My Kangaroo?) щороку ми мали задачу, пов'язану з кенгуру! Ми хотіли б ознайомити вас з усіма цими задачами, але якщо робити так щороку, то в змаганні 3025 року умова однієї задачі може займати 500 сторінок. Тому цього разу ми їх пропустимо. До того ж ви, можливо, вже бачили їх у пробному турі.

Тепер, у змаганні 2025 року, як усі й очікували, задача про кенгуру знову повернулася! Ми не знаємо, чому автори задач так одержимі кенгуру, але задача полягає в наступному:

Вам дано сітку з $n$ рядків та $m$ стовпців. У клітинці в $i_h$-му рядку та $j_h$-му стовпці є яма. Усі інші клітинки порожні, і в кожній клітинці стоїть один кенгуру.

Аналогічно, керування кенгуру здійснюється натисканням кнопок U, D, L, R на клавіатурі. Усі кенгуру рухатимуться одночасно відповідно до натиснутої кнопки. Зокрема, для будь-якого кенгуру, розташованого в клітинці в $i$-му рядку та $j$-му стовпці, що позначається $(i, j)$:

1. Кнопка U: він переміститься в $(i - 1, j)$.
2. Кнопка D: він переміститься в $(i + 1, j)$.
3. Кнопка L: він переміститься в $(i, j - 1)$.
4. Кнопка R: він переміститься в $(i, j + 1)$.

Якщо кенгуру потрапляє в яму (тобто $i = i_h$ та $j = j_h$) або виходить за межі сітки, він видаляється із сітки.

Проблема полягає в тому, що точні значення $i_h$ та $j_h$ невідомі. Ваше завдання — знайти положення ями за допомогою щонайбільше $(n + m + 10)$ запитів. У кожному запиті ви можете натиснути одну кнопку (U, D, L або R). Інтерактор виведе у відповідь ціле число $t$, що вказує на кількість кенгуру, які залишилися після натискання кнопки.

Зауважте, що інтерактор не є адаптивним, тобто відповідь для кожного тестового випадку визначена заздалегідь.

Вхідні дані

Є декілька тестових випадків. Перший рядок вхідних даних містить ціле число $T$ ($1 \le T \le 100$), що вказує на кількість тестових випадків. Для кожного тестового випадку:

Перший рядок містить два цілі числа $n$ та $m$ ($3 \le n, m \le 30$), що вказують на кількість рядків і стовпців у сітці.

Протокол взаємодії

Щоб зробити запит, виведіть один рядок. Спочатку виведіть ?, потім пробіл, а далі одну велику англійську літеру (U, D, L або R). Після очищення буфера виводу (flush) ваша програма повинна зчитати одне ціле число $t$, що вказує на відповідь на ваш запит. Нагадаємо, що ви можете зробити щонайбільше $(n + m + 10)$ запитів для одного тестового випадку.

Якщо ви хочете вгадати положення ями, виведіть один рядок. Спочатку виведіть !, потім пробіл, а далі два цілі числа $i_h$ та $j_h$ ($1 \le i_h \le n$, $1 \le j_h \le m$), розділені пробілом, що вказують на положення. Після очищення буфера виводу ваша програма повинна продовжити обробку наступного тестового випадку або негайно завершити роботу, якщо тестових випадків більше немає. Зауважте, що ваша відповідь не вважається запитом.

Щоб очистити буфер виводу, ви можете використовувати:

• fflush(stdout) (якщо ви використовуєте printf) або cout.flush() (якщо ви використовуєте cout) у C та C++.
• System.out.flush() у Java та Kotlin.
• sys.stdout.flush() у Python.

Приклади

2
3 4

7

3

4 3

8

5

? L

? D

! 2 3

? U

? R

! 1 1