นี่คือปัญหาแบบโต้ตอบ (Interactive Problem)

หลังจากประสบความสำเร็จอย่างยิ่งใหญ่ตั้งแต่ปี 2018 ถึง 2024 มหาวิทยาลัยการบินและอวกาศหนานจิง (NUAA) จะเป็นเจ้าภาพจัดการแข่งขัน International Collegiate Programming Contest (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$ เป็นคำตอบ ซึ่งระบุจำนวนจิงโจ้ที่เหลืออยู่หลังจากที่คุณกดปุ่มนั้น

สังเกตว่าโปรแกรมโต้ตอบไม่ได้ปรับเปลี่ยนตามคำถาม (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$) คั่นด้วยช่องว่างเพื่อระบุตำแหน่ง หลังจาก flush ข้อมูลส่งออกแล้ว โปรแกรมของคุณจะต้องดำเนินการกรณีทดสอบถัดไปทันที หรือจบการทำงานทันทีหากไม่มีกรณีทดสอบเหลืออยู่แล้ว สังเกตว่าการทายคำตอบไม่นับเป็นจำนวนครั้งของการถามคำถาม

ในการ flush ข้อมูลส่งออก คุณสามารถใช้:

• 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