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