Este es un problema interactivo.

Tras el gran éxito obtenido entre 2018 y 2024, la Universidad de Aeronáutica y Astronáutica de Nankín (NUAA) acogerá por octava vez consecutiva la fase regional de Nankín del International Collegiate Programming Contest (ICPC).

El equipo Power of Two y el equipo Three Hold Two ganaron el título de campeón para la Universidad de Tsinghua en 2018 y 2019. En 2020, 2021 y 2022, el equipo Inverted Cross de la Universidad de Pekín consiguió el tricampeonato, mientras que en 2023 otro equipo de la Universidad de Pekín, Reborn as a Vegetable Dog, se alzó con el título. En 2024, el equipo Afterlife de la Universidad de Zhejiang obtuvo el primer puesto.

Este año participan en el concurso alrededor de $335$ equipos. Se otorgarán como máximo $33$ medallas de oro, $66$ medallas de plata y $99$ medallas de bronce (ten en cuenta que estas cifras son solo de referencia). ¡Estamos deseando ver la extraordinaria actuación de los participantes! También queremos expresar nuestra gratitud por el arduo trabajo realizado por todo el personal y los voluntarios de este concurso. ¡Gracias a todos por vuestra gran contribución a este certamen!

Foto tomada en el 2023 ICPC Asia Nanjing Regional Contest

En el concurso de 2018, el problema K, Kangaroo Puzzle, pedía a los concursantes construir una secuencia de operaciones para el juego:

El rompecabezas es una cuadrícula con $n$ filas y $m$ columnas ($1 \le n, m \le 20$), y hay algunos (al menos $2$) canguros situados en la cuadrícula. El objetivo del jugador es controlarlos para que se reúnan en una misma celda. Hay muros en algunas celdas y los canguros no pueden entrar en las celdas con muros. Las demás celdas están vacías. Los canguros pueden moverse de una celda vacía a una celda vacía adyacente en cuatro direcciones: arriba, abajo, izquierda y derecha.

Al principio hay exactamente un canguro en cada celda vacía, y el jugador puede controlar a los canguros pulsando los botones U, D, L, R del teclado. Los canguros se moverán simultáneamente según el botón que pulses.

El concursante debe construir una secuencia de operaciones de a lo sumo $5 \times 10^4$ pasos formada únicamente por U, D, L, R para lograr el objetivo.

En el concurso de 2020, el problema A, Ah, It’s Yesterday Once More, pedía a los concursantes construir un mapa de entrada para hackear el siguiente código del problema descrito anteriormente:

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

Además, en el concurso de 2021 (Problema A, Oops, It’s Yesterday Twice More), el concurso de 2022 (Problema A, Stop, Yesterday Please No More), el concurso de 2023 (Problema A, Cool, It’s Yesterday Four Times More) y el concurso de 2024 (Problema A, Hey, Have You Seen My Kangaroo?), ¡todos los años tenemos un problema relacionado con los canguros! Nos gustaría presentaros todos estos problemas, pero si lo hacemos cada año, es posible que en el concurso de 3025 tengamos un enunciado de 500 páginas para un solo problema. Por lo tanto, esta vez los omitimos. Además, puede que ya los hayas visto en el concurso de práctica.

Ahora, en el concurso de 2025, como todo el mundo espera, ¡el problema de los canguros está de vuelta! No sabemos por qué los autores están tan obsesionados con los canguros, pero el problema es el siguiente:

Se te da una cuadrícula con $n$ filas y $m$ columnas. Hay un agujero en la celda de la $i_h$-ésima fila y la $j_h$-ésima columna. Todas las demás celdas están vacías y hay un canguro en cada una de ellas.

Del mismo modo, los canguros se controlan pulsando el botón U, D, L, R del teclado. Todos los canguros se moverán simultáneamente según el botón pulsado. Específicamente, para cualquier canguro situado en la celda de la $i$-ésima fila y la $j$-ésima columna, denotada por $(i, j)$:

1. Botón U: se moverá a $(i - 1, j)$.
2. Botón D: se moverá a $(i + 1, j)$.
3. Botón L: se moverá a $(i, j - 1)$.
4. Botón R: se moverá a $(i, j + 1)$.

Si un canguro pisa el agujero (es decir, $i = i_h$ y $j = j_h$) o sale de la cuadrícula, será eliminado de la cuadrícula.

El problema es que no se conoce el valor exacto de $i_h$ y $j_h$. Tu tarea consiste en encontrar la posición del agujero con a lo sumo $(n + m + 10)$ consultas. En cada consulta puedes pulsar un botón (U, D, L o R). El interactor imprimirá un entero $t$ como respuesta, indicando el número de canguros que quedan después de pulsar el botón.

Ten en cuenta que el interactor no es adaptativo, lo que significa que la respuesta para cada caso de prueba está predeterminada.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1 \le T \le 100$) que indica el número de casos de prueba. Para cada caso de prueba:

La primera línea contiene dos enteros $n$ y $m$ ($3 \le n, m \le 30$) que indican el número de filas y columnas de la cuadrícula.

Protocolo de interacción

Para hacer una consulta, imprime una línea. Primero imprime ? seguido de un espacio, y luego imprime una letra mayúscula inglesa (U, D, L o R). Después de vaciar el búfer de salida (flush), tu programa debe leer un único entero $t$ que indica la respuesta a tu consulta. Recuerda que puedes hacer como máximo $(n + m + 10)$ consultas por caso de prueba.

Si quieres adivinar la posición del agujero, imprime una línea. Primero imprime ! seguido de un espacio, y luego imprime dos enteros $i_h$ y $j_h$ ($1 \le i_h \le n$, $1 \le j_h \le m$) separados por un espacio indicando la posición. Después de vaciar el búfer de salida, tu programa debe continuar procesando el siguiente caso de prueba, o terminar inmediatamente si no hay más casos de prueba. Ten en cuenta que tu conjetura final no cuenta como una consulta.

Para vaciar el búfer de salida, puedes usar:

• fflush(stdout) (si usas printf) o cout.flush() (si usas cout) en C y C++.
• System.out.flush() en Java y Kotlin.
• sys.stdout.flush() en Python.

Ejemplos

2
3 4

7

3

4 3

8

5

? L

? D

! 2 3

? U

? R

! 1 1