Бұл — интерактивті есеп.

2018 жылдан 2024 жылға дейінгі зор табыстан кейін Нанкин аэронавтика және астронавтика университеті (NUAA) сегізінші рет қатарынан Студенттер арасындағы халықаралық бағдарламалау олимпиадасының (ICPC) Нанкин аймақтық кезеңін өткізеді.

2018 және 2019 жылдары Power of Two және Three Hold Two командалары Цинхуа университетіне чемпиондық атақ әپرген болатын. 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 батырмаларын басу арқылы кенгуруларды басқара алады. Кенгурулар сіз басқан батырмаға сәйкес бір мезгілде қозғалады.

Қатысушы мақсатқа жету үшін тек U, D, L, R таңбаларынан тұратын, ұзындығы ең көбі $5 \times 10^4$ қадам болатын операциялар тізбегін құруы керек.

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$ бүтін санын шығарады.

Интерактор бейімделгіш (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