Это интерактивная задача.

После огромного успеха с 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