На шахматной доске размером $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)$, который бьёт единственного Слайма. Поскольку после этого рядом со Слаймом нет доступных пустых клеток, он не может разделиться. Игра выиграна.