Na szachownicy o $10$ wierszach i $9$ kolumnach rozgrywana jest gra o nazwie „Qi Men Xiang Qi”. Każda ze stron ma kilka bierek, a różne bierki mają różne właściwości. Używamy współrzędnych $(x, y)$ do oznaczenia pozycji w $x$-tym wierszu i $y$-tej kolumnie szachownicy.
Nasza strona posiada kilka Wież (Rooks) i kilka Skoczków (Knights), a także umiejętność Zmiany Kształtu (Shape-shifting). Zasady ruchu tych dwóch rodzajów bierek oraz działanie umiejętności opisano poniżej:
- Załóżmy, że Wieża znajduje się na współrzędnych $(a, b)$. Jeśli w jednej akcji przemieszcza się na współrzędne $(c, d)$ na szachownicy, muszą być spełnione następujące warunki:
- Na polu $(c, d)$ nie ma naszych bierek. Oznacza to, że nie może ona zbijać naszych bierek ani nakładać się na nie.
- $c = a$ lub $d = b$, ale $(a, b) \neq (c, d)$. Oznacza to, że może poruszać się wzdłuż wiersza lub kolumny, w której się znajduje, ale nie może pozostać w tym samym miejscu.
- Pomiędzy $(a, b)$ a $(c, d)$ nie może znajdować się żadna inna bierka. Oznacza to, że podczas ruchu nie może przeskakiwać nad innymi bierkami.
- Załóżmy, że Skoczek znajduje się na współrzędnych $(a, b)$. Jeśli w jednej akcji przemieszcza się na współrzędne $(c, d)$ na szachownicy, muszą być spełnione następujące warunki:
- Na polu $(c, d)$ nie ma naszych bierek. Oznacza to, że nie może on zbijać naszych bierek ani nakładać się na nie.
- $\{|a - c|, |b - d|\} = \{1, 2\}$. Tutaj $\{\dots\}$ oznacza zbiór nieuporządkowany. Odpowiada to tradycyjnemu ruchowi szachowemu w kształcie litery „L” (zauważ, że w tym zadaniu nie występuje blokowanie skoczka).
- Zmiana Kształtu: Może być użyta jako jedna akcja do zamiany pozycji dowolnych dwóch naszych bierek. Nie ma limitu liczby użyć.
Przeciwnik posiada kilka Szlamów (Slimes). Szlamy nie mogą się poruszać, ale mają następujące właściwości:
- Załóżmy, że Szlam znajduje się na współrzędnych $(a, b)$. Kiedy zostaje zbity i usunięty, natychmiast się dzieli, generując po jednym Szlamie na każdym z czterech sąsiednich pól (góra, dół, lewo, prawo). Dokładniej, na tych czterech sąsiednich polach nowe szlamy nie powstaną na pozycjach, na których znajdują się już jakiekolwiek inne bierki, ani poza granicami szachownicy.
- Szlamy powstałe w wyniku podziału mają takie same właściwości podziału i nie ma limitu liczby podziałów.
Po wykonaniu ruchu bierką, jeśli nałoży się ona na bierkę przeciwnika, następuje zbicie i usunięcie bierki przeciwnika. Warunkiem zwycięstwa w grze jest zbicie wszystkich Szlamów przeciwnika, tak aby na szachownicy nie pozostały żadne bierki wroga.
Podczas gry Xiao Biao zauważył, że chociaż przeciwnik nie może poruszać swoimi bierkami, naszej stronie nadal trudno jest czysto zbić wszystkie Szlamy, ponieważ jest ich dużo i dzielą się bardzo wydajnie, co często prowadzi do powstawania jeszcze większej liczby szlamów i utrudnia Xiao Biao ocenę, czy zwycięstwo w tej grze jest w ogóle możliwe. Zwrócił się więc do Ciebie — osoby biegłej w strategii i analizie — z nadzieją, że pomożesz mu ustalić, czy istnieje strategia pozwalająca osiągnąć zwycięstwo w co najwyżej $10^4$ ruchach. Jeśli taka wygrywająca strategia istnieje, wypisz operacje dla każdego kroku.
Wejście
Wejście składa się z $10$ wierszy, z których każdy zawiera napis o długości $9$, reprezentujący sytuację na szachownicy. Znak . oznacza puste pole; znak C oznacza naszą Wieżę; znak M oznacza naszego Skoczka; a znak S oznacza Szlam przeciwnika.
Każdy rodzaj znaku może wystąpić wielokrotnie. Dane gwarantują, że na szachownicy znajduje się co najmniej jeden Szlam oraz co najmniej jedna nasza bierka.
Wyjście
Jeśli nie istnieje strategia pozwalająca wygrać w co najwyżej $10^4$ ruchach:
- Wypisz w pojedynczym wierszu napis
WuJie.
Jeśli istnieje strategia pozwalająca wygrać w co najwyżej $10^4$ ruchach:
- Najpierw wypisz w pojedynczym wierszu napis
YouJie. - Następnie wypisz liczbę całkowitą $s$, oznaczającą liczbę akcji.
- Potem wypisz $s$ wierszy, z których każdy zawiera cztery liczby całkowite $a, b, c, d$, oznaczające, że nasza bierka znajdująca się obecnie na polu $(a, b)$ zostaje przesunięta na pozycję $(c, d)$. W szczególności, jeśli na obu pozycjach $(a, b)$ oraz $(c, d)$ znajdują się już nasze bierki, akcja ta jest traktowana jako Zmiana Kształtu, co oznacza, że te dwie bierki zamieniają się miejscami.
- Twoja strategia musi gwarantować, że po wykonaniu wszystkich akcji na szachownicy nie pozostanie żaden Szlam.
Jeśli istnieje wiele różnych poprawnych rozwiązań, można wypisać dowolne z nich.
Rozwiązania niespełniające wymagań formatu, niezgodne z zasadami ruchu bierek lub wskazujące brak naszej bierki na pozycji $(a, b)$ zostaną uznane za błędne.
Przykłady
Wejście 1
...CSC... ...CCCM.. ......... ......... ......... ......... ......... ......... ......... .........
Wyjście 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
Wejście 2
SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSCSSSS
Wyjście 2
WuJie
Uwaga
Wyjście dla przykładu $1$ pokazuje kilka poprawnych operacji i ostatecznie zbija wszystkie szlamy.
- Kroki od $1$ do $3$ pokazują Wieżę na $(1, 4)$ poruszającą się w lewo, wybierając ruch o jedno pole naraz i ostatecznie lądując na $(1, 1)$.
- Krok $4$ demonstruje operację Zmiany Kształtu, zamieniającą Wieżę na $(1, 1)$ z Wieżą na $(2, 4)$.
- Krok $5$ pokazuje Wieżę na $(2, 4)$ poruszającą się w górę na $(1, 4)$.
- Ostatni krok pokazuje Skoczka skaczącego z $(2, 7)$ na $(1, 5)$, aby zbić jedynego Szlama. Ponieważ po tym ruchu nie ma żadnych dostępnych pustych pól sąsiadujących ze Szlamem, nie może się on podzielić. Gra zostaje wygrana.