Ceci est un problème interactif.

Après le grand succès rencontré de 2018 à 2024, l'Université d'aéronautique et d'astronautique de Nankin (NUAA) accueillera pour la huitième fois consécutive le concours régional de Nankin de l'International Collegiate Programming Contest (ICPC).

L'équipe Power of Two et l'équipe Three Hold Two ont remporté le titre de champion pour l'Université Tsinghua en 2018 et 2019. En 2020, 2021 et 2022, l'équipe Inverted Cross de l'Université de Pékin a réalisé le triplé, tandis qu'en 2023, une autre équipe de l'Université de Pékin, Reborn as a Vegetable Dog, a remporté le titre. En 2024, l'équipe Afterlife de l'Université du Zhejiang a pris la première place.

Cette année, environ $335$ équipes participent au concours. Au plus $33$ médailles d'or, $66$ médailles d'argent et $99$ médailles de bronze seront décernées (notez que ces chiffres ne sont donnés qu'à titre indicatif). Nous avons hâte d'assister aux performances exceptionnelles des participants ! Nous tenons également à exprimer notre gratitude envers tout le personnel et les bénévoles pour leur travail acharné lors de ce concours. Merci à tous pour votre grande contribution à ce concours !

Photo prise lors du concours régional ICPC Asie de Nankin 2023

Lors du concours de 2018, le problème K, Kangaroo Puzzle, demandait aux participants de construire une séquence d'opérations pour le jeu suivant :

Le puzzle est une grille de $n$ lignes et $m$ colonnes ($1 \le n, m \le 20$), dans laquelle se trouvent plusieurs (au moins $2$) kangourous. Le but du joueur est de les contrôler pour les rassembler. Certaines cases contiennent des murs et les kangourous ne peuvent pas entrer dans ces cases. Les autres cases sont vides. Les kangourous peuvent se déplacer d'une case vide vers une case vide adjacente dans quatre directions : haut, bas, gauche et droite.

Au départ, il y a exactement un kangourou dans chaque case vide, et le joueur peut contrôler les kangourous en appuyant sur les touches U, D, L, R du clavier. Les kangourous se déplacent simultanément selon la touche sur laquelle vous appuyez.

Le participant doit construire une séquence d'opérations d'au plus $5 \times 10^4$ étapes composée uniquement de U, D, L, R pour atteindre l'objectif.

Lors du concours de 2020, le problème A, Ah, It’s Yesterday Once More, demandait aux participants de construire une carte d'entrée pour mettre en échec (hacker) le code suivant du problème décrit précédemment :

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

De plus, lors du concours de 2021 (Problème A, Oops, It’s Yesterday Twice More), du concours de 2022 (Problème A, Stop, Yesterday Please No More), du concours de 2023 (Problème A, Cool, It’s Yesterday Four Times More) et du concours de 2024 (Problème A, Hey, Have You Seen My Kangaroo?), nous avons eu chaque année un problème lié aux kangourous ! Nous aimerions vous présenter tous ces problèmes, mais si nous le faisons chaque année, nous risquons d'avoir un énoncé de 500 pages pour un seul problème lors du concours de 3025. Par conséquent, nous les omettons cette fois-ci. D'ailleurs, vous les avez peut-être déjà vus lors du concours d'entraînement.

Maintenant, lors du concours de 2025, comme tout le monde s'y attend, le problème des kangourous est de retour ! Nous ne savons pas pourquoi les auteurs des sujets sont si obsédés par les kangourous, mais le problème est le suivant :

On vous donne une grille de $n$ lignes et $m$ colonnes. Il y a un trou dans la case située à la $i_h$-ème ligne et la $j_h$-ème colonne. Toutes les autres cases sont vides et un kangourou se tient dans chacune d'elles.

De même, les kangourous sont contrôlés en appuyant sur les touches U, D, L, R du clavier. Tous les kangourous se déplacent simultanément selon la touche pressée. Plus précisément, pour tout kangourou situé dans la case de la $i$-ème ligne et de la $j$-ème colonne, notée $(i, j)$ :

1. Touche U : il se déplace en $(i - 1, j)$.
2. Touche D : il se déplace en $(i + 1, j)$.
3. Touche L : il se déplace en $(i, j - 1)$.
4. Touche R : il se déplace en $(i, j + 1)$.

Si un kangourou marche sur le trou (c'est-à-dire $i = i_h$ et $j = j_h$) ou sort de la grille, il est retiré de la grille.

Le problème est que les valeurs exactes de $i_h$ et $j_h$ sont inconnues. Votre tâche consiste à trouver la position du trou en au plus $(n + m + 10)$ requêtes. Pour chaque requête, vous pouvez appuyer sur une touche (U, D, L ou R). L'interacteur affichera un entier $t$ en guise de réponse, indiquant le nombre de kangourous restants après que vous avez appuyé sur la touche.

Notez que l'interacteur n'est pas adaptatif, ce qui signifie que la réponse pour chaque cas de test est prédéterminée.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un entier $T$ ($1 \le T \le 100$) indiquant le nombre de cas de test. Pour chaque cas de test :

La première ligne contient deux entiers $n$ et $m$ ($3 \le n, m \le 30$) indiquant le nombre de lignes et de colonnes de la grille.

Protocole d'interaction

Pour poser une requête, affichez une ligne. Affichez d'abord ? suivi d'une espace, puis une lettre majuscule anglaise (U, D, L ou R). Après avoir vidé le tampon de sortie (flush), votre programme doit lire un seul entier $t$ indiquant la réponse à votre requête. Rappelez-vous que vous pouvez poser au plus $(n + m + 10)$ requêtes par cas de test.

Si vous souhaitez deviner la position du trou, affichez une ligne. Affichez d'abord ! suivi d'une espace, puis deux entiers $i_h$ et $j_h$ ($1 \le i_h \le n$, $1 \le j_h \le m$) séparés par une espace indiquant la position. Après avoir vidé le tampon de sortie, votre programme doit continuer à traiter le cas de test suivant, ou se terminer immédiatement s'il n'y a plus de cas de test. Notez que votre réponse finale ne compte pas comme une requête.

Pour vider votre tampon de sortie, vous pouvez utiliser :

• fflush(stdout) (si vous utilisez printf) ou cout.flush() (si vous utilisez cout) en C et C++.
• System.out.flush() en Java et Kotlin.
• sys.stdout.flush() en Python.

Exemples

2
3 4

7

3

4 3

8

5

? L

? D

! 2 3

? U

? R

! 1 1