זוהי בעיה אינטראקטיבית.

לאחר ההצלחה הגדולה בין השנים 2018 ל-2024, אוניברסיטת נאנג'ינג לאווירונאוטיקה ואסטרונאוטיקה (NUAA) תארח את התחרות האזורית של נאנג'ינג במסגרת התחרות הבינלאומית לתכנות לסטודנטים (ICPC) בפעם השמינית ברציפות.

הקבוצות Power of Two ו-Three Hold Two זכו בתואר האליפות עבור אוניברסיטת צינגהואה בשנים 2018 ו-2019. בשנים 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 במקלדת. הקנגורואים ינועו בו-זמנית בהתאם לכפתור שלחצתם.

על המתחרה לבנות סדרת פעולות באורך של לכל היותר $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?), בכל שנה הייתה לנו בעיה הקשורה לקנגורואים! היינו שמחים להציג לכם את כל הבעיות הללו, אך אם נעשה זאת בכל שנה, בתחרות של שנת 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$ כתשובה, המציין את מספר הקנגורואים שנותרו לאחר שלחצתם על הכפתור.

שימו לב שהאינטראקטור אינו אדפטיבי, כלומר התשובה עבור כל מקרה בדיקה נקבעת מראש.

קלט

ישנם מספר מקרי בדיקה. השורה הראשונה של הקלט מכילה מספר שלם $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