على رقعة شطرنج مكونة من $10$ صفوف و $9$ أعمدة، تُلعب لعبة تسمى "تشي مين شيانغ تشي". يمتلك كل طرف عدة قطع، وتتميز القطع المختلفة بخصائص مختلفة. نستخدم الإحداثيات $(x, y)$ لتمثيل الموضع في الصف الـ $x$ والعمود الـ $y$ من رقعة الشطرنج.
يمتلك طرفنا عدة قلاع (Rooks) وعدة أحصنة (Knights)، بالإضافة إلى مهارة تغيير الشكل (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" (لاحظ أنه لا توجد قاعدة إعاقة الحصان في هذه المسألة).
- تغيير الشكل: يمكن استخدام هذه المهارة كإجراء واحد لتبديل موضعي أي قطعتين صديقتين. لا يوجد حد لعدد مرات الاستخدام.
يمتلك العدو عدة سلايم (Slimes). لا يمكن للسلايم التحرك ولكن لديه الخصائص التالية:
- لنفترض أن السلايم يقع عند الإحداثيات $(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)$ لأسر السلايم الوحيد. وبما أنه لا توجد مواضع فارغة صالحة مجاورة للسلايم بعد ذلك، فلا يمكنه الانقسام. يتم الفوز باللعبة.