هذه مسألة تفاعلية.

بعد النجاح الكبير الذي تحقق من عام 2018 إلى عام 2024، ستستضيف جامعة نانجينغ للملاحة الجوية والفضائية (NUAA) المسابقة الإقليمية في نانجينغ التابعة لـ المسابقة الدولية للبرمجة الجامعية (ICPC) للمرة الثامنة على التوالي.

فاز فريق Power of Two وفريق Three Hold Two بلقب البطولة لصالح جامعة تسينغهوا في عامي 2018 و2019. وفي أعوام 2020 و2021 و2022، فاز فريق Inverted Cross من جامعة بكين بلقب البطولة ثلاث مرات متتالية، بينما فاز فريق آخر من جامعة بكين وهو Reborn as a Vegetable Dog باللقب في عام 2023. وفي عام 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، من المتسابقين بناء خريطة إدخال لكسر (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?)، كان لدينا في كل عام مسألة تتعلق بحيوانات الكنغر! نود أن نقدم لكم جميع هذه المسائل، ولكن إذا فعلنا ذلك كل عام، فقد يصبح لدينا نص مسألة من 500 صفحة لمسألة واحدة فقط في مسابقة عام 3025. لذلك، سنتجاوزها هذه المرة. بالإضافة إلى ذلك، ربما تكون قد رأيتها بالفعل في المسابقة التجريبية.

الآن، في مسابقة عام 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$ كإجابة، يشير إلى عدد حيوانات الكنغر المتبقية بعد ضغطك على الزر.

لاحظ أن المتفاعل غير تكيفي (non-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$) مفصولين بمسافة للإشارة إلى الموقع. بعد تفريغ مخزن الإخراج المؤقت، يجب أن يواصل برنامجك معالجة حالة الاختبار التالية، أو الخروج فورًا إذا لم يتبقَّ المزيد من حالات الاختبار. لاحظ أن تخمينك لا يُحتسب كاستعلام.

لتفريغ مخزن الإخراج المؤقت، يمكنك استخدام:

• 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