이 문제는 인터랙티브 문제입니다.

2018년부터 2024년까지의 큰 성공에 힘입어, 난징항공항천대학(NUAA)은 8년 연속으로 국제 대학생 프로그래밍 경시대회(ICPC) 난징 리저널을 개최합니다.

2018년과 2019년에는 Power of Two 팀과 Three Hold Two 팀이 칭화대학교에 우승을 안겨주었습니다. 2020년, 2021년, 2022년에는 베이징대학교의 Inverted Cross 팀이 3연패를 달성했으며, 2023년에는 베이징대학교의 또 다른 팀인 Reborn as a Vegetable Dog 팀이 우승을 차지했습니다. 2024년에는 저장대학교의 Afterlife 팀이 1위를 차지했습니다.

올해에는 약 $335$개 팀이 대회에 참가합니다. 최대 $33$개의 금메달, $66$개의 은메달, $99$개의 동메달이 수여될 예정입니다(이 숫자는 참고용입니다). 참가자 여러분의 뛰어난 활약을 기대합니다! 또한 이번 대회를 위해 열심히 일해주신 모든 스태프와 자원봉사자분들께도 감사의 말씀을 전하고 싶습니다. 대회를 위해 크게 기여해 주신 모든 분께 감사드립니다!

2023 ICPC 아시아 난징 리저널 대회에서 촬영된 사진

2018년 대회의 K번 문제인 Kangaroo Puzzle에서는 참가자들에게 다음 게임을 위한 조작 수열을 구성하도록 요구했습니다:

퍼즐은 $n$개의 행과 $m$개의 열($1 \le n, m \le 20$)로 이루어진 격자판이며, 퍼즐 안에는 몇 마리(최소 $2$마리)의 캥거루가 서 있습니다. 플레이어의 목표는 캥거루들을 조종해 한곳에 모이게 하는 것입니다. 일부 칸에는 벽이 있으며, 캥거루는 벽이 있는 칸으로 들어갈 수 없습니다. 나머지 칸들은 비어 있습니다. 캥거루는 빈칸에서 상, 하, 좌, 우 네 방향의 인접한 빈칸으로 이동할 수 있습니다.

처음에는 모든 빈칸에 정확히 한 마리의 캥거루가 있으며, 플레이어는 키보드의 U, D, L, R 버튼을 눌러 캥거루들을 조종할 수 있습니다. 캥거루들은 누른 버튼에 따라 동시에 이동합니다.

참가자는 목표를 달성하기 위해 U, D, L, R로만 구성된 최대 $5 \times 10^4$번의 조작 수열을 만들어야 합니다.

2020년 대회의 A번 문제인 Ah, It’s Yesterday Once More에서는 앞서 설명한 문제에 대한 아래 코드를 핵(hack)하기 위한 입력 지도를 구성하도록 요구했습니다:

#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$를 답으로 출력합니다.

인터랙터는 적응형(adaptive)이 아닙니다. 즉, 각 테스트 케이스의 정답은 미리 정해져 있습니다.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $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$)를 공백으로 구분하여 출력합니다. 출력을 플러시한 후, 프로그램은 다음 테스트 케이스를 계속 처리하거나 더 이상 테스트 케이스가 없으면 즉시 종료해야 합니다. 추측은 질의 횟수에 포함되지 않습니다.

출력을 플러시하기 위해 다음을 사용할 수 있습니다:

• C와 C++에서는 fflush(stdout) (printf를 사용하는 경우) 또는 cout.flush() (cout를 사용하는 경우).
• Java와 Kotlin에서는 System.out.flush().
• Python에서는 sys.stdout.flush().

예제

2
3 4

7

3

4 3

8

5

? L

? D

! 2 3

? U

? R

! 1 1