บนกระดานหมากรุกขนาด $10$ แถว $9$ คอลัมน์ กำลังมีการเล่นเกมที่เรียกว่า "Qi Men Xiang Qi" แต่ละฝ่ายมีหมากหลายตัว และหมากแต่ละชนิดก็มีลักษณะเฉพาะที่แตกต่างกัน เราใช้พิกัด $(x, y)$ แทนตำแหน่งในแถวที่ $x$ และคอลัมน์ที่ $y$ ของกระดานหมากรุก
ฝ่ายของเรามีเรือ (Rook) หลายตัว และม้า (Knight) หลายตัว รวมถึงทักษะการสลับร่าง (Shape-shifting) วิธีการเดินของหมากทั้งสองชนิดนี้และทักษะมีรายละเอียดดังต่อไปนี้:
- สมมติว่าเรืออยู่ที่พิกัด $(a, b)$ หากมันเดินไปยังพิกัด $(c, d)$ บนกระดานหมากรุกในหนึ่งการกระทำ จะต้องเป็นไปตามเงื่อนไขต่อไปนี้:
- ต้องไม่มีหมากฝ่ายเดียวกันอยู่ที่ $(c, d)$ นั่นคือ มันไม่สามารถกินหมากฝ่ายเดียวกัน และไม่สามารถซ้อนทับกับหมากฝ่ายเดียวกันได้
- $c = a$ หรือ $d = b$ แต่ $(a, b) \neq (c, d)$ นั่นคือ มันสามารถเดินไปตามแถวหรือคอลัมน์ที่มันอยู่ได้ แต่ไม่สามารถหยุดอยู่ที่ตำแหน่งเดิมได้
- ต้องไม่มีหมากตัวอื่นใดอยู่ระหว่าง $(a, b)$ และ $(c, d)$ นั่นคือ มันไม่สามารถกระโดดข้ามหมากตัวอื่นในขณะเดินได้
- สมมติว่าม้าอยู่ที่พิกัด $(a, b)$ หากมันเดินไปยังพิกัด $(c, d)$ บนกระดานหมากรุกในหนึ่งการกระทำ จะต้องเป็นไปตามเงื่อนไขต่อไปนี้:
- ต้องไม่มีหมากฝ่ายเดียวกันอยู่ที่ $(c, d)$ นั่นคือ มันไม่สามารถกินหมากฝ่ายเดียวกัน และไม่สามารถซ้อนทับกับหมากฝ่ายเดียวกันได้
- $\{|a - c|, |b - d|\} = \{1, 2\}$ ในที่นี้ $\{\dots\}$ แทนเซตที่ไม่มีลำดับ ซึ่งสอดคล้องกับการเดินของม้าเป็นรูปตัว "L" ในหมากรุกดั้งเดิม (หมายเหตุว่าไม่มีการ "ขัดขาม้า" ในโจทย์ข้อนี้)
- การสลับร่าง (Shape-shifting): สามารถใช้เป็นหนึ่งการกระทำเพื่อสลับตำแหน่งของหมากฝ่ายเดียวกันสองตัวใดๆ ก็ได้ โดยไม่จำกัดจำนวนครั้งในการใช้
ฝ่ายศัตรูมีสไลม์ (Slime) หลายตัว สไลม์ไม่สามารถเคลื่อนที่ได้ แต่มีลักษณะเฉพาะดังต่อไปนี้:
- สมมติว่าสไลม์อยู่ที่พิกัด $(a, b)$ เมื่อมันถูกกินและนำออกจากกระดาน มันจะแบ่งตัวทันที โดยสร้างสไลม์หนึ่งตัวในแต่ละตำแหน่งที่อยู่ติดกันทั้งสี่ทิศทาง (บน ล่าง ซ้าย ขวา) โดยเฉพาะอย่างยิ่ง ในสี่ตำแหน่งที่อยู่ติดกันนี้ จะไม่มีการสร้างสไลม์ใหม่ในตำแหน่งที่มีหมากตัวอื่นอยู่แล้ว หรือตำแหน่งที่อยู่นอกขอบเขตของกระดานหมากรุก
- สไลม์ที่เกิดจากการแบ่งตัวจะมีลักษณะการแบ่งตัวแบบเดียวกัน และไม่จำกัดจำนวนครั้งของการแบ่งตัว
หลังจากเดินหมากแล้ว หากหมากซ้อนทับกับหมากของศัตรู จะเป็นการกินหมากและนำหมากของศัตรูออกจากกระดาน เงื่อนไขการชนะของเกมคือการกินสไลม์ของศัตรูทั้งหมด เพื่อรับประกันว่าจะไม่มีหมากของศัตรูเหลืออยู่บนกระดานหมากรุก
ในระหว่างเล่นเกม เสี่ยวเปียวพบว่าแม้ศัตรูจะไม่สามารถเดินหมากของตนได้ แต่ฝ่ายของเราก็ยังยากที่จะกินสไลม์ทั้งหมดได้อย่างหมดจด เนื่องจากพวกมันมีจำนวนมากและแบ่งตัวได้อย่างมีประสิทธิภาพสูง ซึ่งมักจะนำไปสู่การสร้างสไลม์เพิ่มมากขึ้น ทำให้เสี่ยวเปียวตัดสินใจได้ยากว่าเกมนี้จะสามารถเอาชนะได้หรือไม่ เขาจึงมาหาคุณซึ่งเชี่ยวชาญด้านกลยุทธ์และการวิเคราะห์ โดยหวังว่าคุณจะช่วยเขาตัดสินใจได้ว่ามีกลยุทธ์ที่จะคว้าชัยชนะภายใน $10^4$ ตาเดินหรือไม่ หากมีกลยุทธ์ที่ชนะดังกล่าว โปรดแสดงผลการดำเนินการในแต่ละขั้นตอน
ข้อมูลนำเข้า
ข้อมูลนำเข้าประกอบด้วย $10$ บรรทัด แต่ละบรรทัดประกอบด้วยสตริงความยาว $9$ แทนสถานการณ์บนกระดานหมากรุก โดยอักขระ . แทนตำแหน่งว่าง; อักขระ C แทนเรือของฝ่ายเรา; อักขระ M แทนม้าของฝ่ายเรา; และอักขระ S แทนสไลม์ของศัตรู
อักขระแต่ละชนิดอาจปรากฏได้หลายครั้ง ข้อมูลรับประกันว่ามีสไลม์อย่างน้อยหนึ่งตัวบนกระดานหมากรุก และมีหมากฝ่ายเดียวกันอย่างน้อยหนึ่งตัว
ข้อมูลส่งออก
หากไม่มีกลยุทธ์ที่จะชนะภายใน $10^4$ ตาเดิน:
- โปรดแสดงผลสตริง
WuJieในบรรทัดเดียว
หากมีกลยุทธ์ที่จะชนะภายใน $10^4$ ตาเดิน:
- ขั้นแรก ให้แสดงผลสตริง
YouJieในบรรทัดเดียว - ถัดไป แสดงผลจำนวนเต็ม $s$ แทนจำนวนการกระทำ
- จากนั้น แสดงผล $s$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มสี่จำนวน $a, b, c, d$ ระบุว่าหมากฝ่ายเดียวกันที่ปัจจุบันอยู่ที่ $(a, b)$ ถูกย้ายไปยังตำแหน่ง $(c, d)$ โดยเฉพาะอย่างยิ่ง หากทั้งสองตำแหน่ง $(a, b)$ และ $(c, d)$ มีหมากฝ่ายเดียวกันอยู่แล้ว การกระทำนี้จะถือเป็นการสลับร่าง ซึ่งระบุว่าหมากทั้งสองตัวนี้สลับตำแหน่งกัน
- กลยุทธ์ของคุณต้องรับประกันว่าหลังจากเสร็จสิ้นการกระทำทั้งหมดแล้ว จะไม่มีสไลม์เหลืออยู่บนกระดานหมากรุก
หากมีคำตอบที่ถูกต้องแตกต่างกันหลายแบบ สามารถแสดงผลแบบใดก็ได้
คำตอบที่ไม่เป็นไปตามข้อกำหนดรูปแบบ ไม่เป็นไปตามกฎการเดินหมาก หรือระบุตำแหน่ง $(a, b)$ ที่ไม่มีหมากอยู่ จะถือว่าไม่ถูกต้อง
ตัวอย่าง
ข้อมูลนำเข้า 1
...CSC... ...CCCM.. ......... ......... ......... ......... ......... ......... ......... .........
ข้อมูลส่งออก 1
YouJie 6 1 4 1 3 1 3 1 2 1 2 1 1 1 1 2 4 2 4 1 4 2 7 1 5
ข้อมูลนำเข้า 2
SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSCSSSS
ข้อมูลส่งออก 2
WuJie
หมายเหตุ
ข้อมูลส่งออกสำหรับตัวอย่างที่ $1$ แสดงการดำเนินการที่ถูกต้องหลายขั้นตอน และสามารถกินสไลม์ทั้งหมดได้ในที่สุด
- ขั้นตอนที่ $1$ ถึง $3$ แสดงเรือที่ $(1, 4)$ เดินไปทางซ้าย โดยเลือกเดินทีละหนึ่งช่อง และไปหยุดอยู่ที่ $(1, 1)$ ในที่สุด
- ขั้นตอนที่ $4$ แสดงการดำเนินการสลับร่าง โดยสลับเรือที่ $(1, 1)$ กับเรือที่ $(2, 4)$
- ขั้นตอนที่ $5$ แสดงเรือที่ $(2, 4)$ เดินขึ้นไปยัง $(1, 4)$
- ขั้นตอนสุดท้ายแสดงม้ากระโดดจาก $(2, 7)$ ไปยัง $(1, 5)$ เพื่อกินสไลม์เพียงตัวเดียว เนื่องจากไม่มีตำแหน่งว่างที่ถูกต้องอยู่ติดกับสไลม์หลังจากนี้ มันจึงไม่สามารถแบ่งตัวได้ ชนะเกมนี้