На шахівниці розміром $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\}$ позначає невпорядковану множину. Це відповідає традиційному шаховому ходу літерою «Г» (зауважте, що в цій задачі немає правила «блокування ходу коня», як у сянці).
- Зміна форми: Може використовуватися як одна дія для обміну місцями будь-яких двох дружніх фігур. Обмежень на кількість використань немає.
Супротивник має декілька Слаймів (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)$, який б'є єдиного Слайма. Оскільки після цього поруч зі Слаймом немає доступних порожніх клітинок, він не може поділитися. Гру виграно.