Trên một bàn cờ có $10$ hàng và $9$ cột, một trò chơi có tên là "Kỳ Môn Tượng Kỳ" đang được diễn ra. Mỗi bên có một số quân cờ, và các quân cờ khác nhau có những đặc điểm khác nhau. Chúng ta sử dụng tọa độ $(x, y)$ để biểu thị vị trí ở hàng thứ $x$ và cột thứ $y$ của bàn cờ.
Bên ta có một số quân Xe (Rook) và một số quân Mã (Knight), cũng như kỹ năng Hoán Đổi Hình Dạng (Shape-shifting). Phương thức di chuyển của hai loại quân cờ này và kỹ năng được mô tả như sau:
- Giả sử quân Xe đang ở tọa độ $(a, b)$. Nếu nó di chuyển đến tọa độ $(c, d)$ trên bàn cờ trong một hành động, các điều kiện sau phải được thỏa mãn:
- Không có quân đồng minh nào tại $(c, d)$. Tức là nó không thể ăn quân đồng minh, cũng không thể chồng lên quân đồng minh.
- $c = a$ hoặc $d = b$, nhưng $(a, b) \neq (c, d)$. Tức là nó có thể di chuyển dọc theo hàng hoặc cột mà nó đang đứng, nhưng không được đứng yên tại chỗ.
- Không được có bất kỳ quân cờ nào khác nằm giữa $(a, b)$ và $(c, d)$. Tức là nó không thể nhảy qua các quân cờ khác khi đang di chuyển.
- Giả sử quân Mã đang ở tọa độ $(a, b)$. Nếu nó di chuyển đến tọa độ $(c, d)$ trên bàn cờ trong một hành động, các điều kiện sau phải được thỏa mãn:
- Không có quân đồng minh nào tại $(c, d)$. Tức là nó không thể ăn quân đồng minh, cũng không thể chồng lên quân đồng minh.
- $\{|a - c|, |b - d|\} = \{1, 2\}$. Ở đây, $\{\dots\}$ biểu thị một tập hợp không có thứ tự. Điều này tương ứng với nước đi hình chữ "L" trong cờ truyền thống (lưu ý rằng không có luật "cản mã" trong bài toán này).
- Hoán Đổi Hình Dạng: Kỹ năng này có thể được sử dụng như một hành động để hoán đổi vị trí của hai quân đồng minh bất kỳ. Không có giới hạn về số lần sử dụng.
Kẻ địch có một số Slime. Slime không thể di chuyển nhưng có các đặc điểm sau:
- Giả sử Slime đang ở tọa độ $(a, b)$. Khi bị ăn và bị loại khỏi bàn cờ, nó sẽ lập tức phân tách, tạo ra một Slime ở mỗi vị trí trong bốn vị trí kề cạnh (trên, dưới, trái, phải). Cụ thể, trong bốn vị trí kề cạnh này, sẽ không có Slime mới nào được tạo ra ở những vị trí đã có bất kỳ quân cờ nào khác hoặc nằm ngoài biên của bàn cờ.
- Các Slime được tạo ra từ sự phân tách cũng có cùng đặc điểm phân tách và không có giới hạn về số lần phân tách.
Sau khi di chuyển các quân cờ, nếu chúng chồng lên quân địch thì sẽ kích hoạt việc ăn quân, loại bỏ quân địch. Điều kiện chiến thắng của trò chơi là ăn tất cả Slime của địch, đảm bảo không còn quân địch nào trên bàn cờ.
Khi chơi trò chơi, Tiểu Tiêu nhận thấy mặc dù kẻ địch không thể di chuyển quân cờ của chúng, bên ta vẫn rất khó tiêu diệt gọn gàng các Slime vì chúng rất đông và phân tách cực kỳ hiệu quả, thường dẫn đến việc sinh ra nhiều Slime hơn nữa, khiến Tiểu Tiêu khó xác định liệu có thể giành chiến thắng trong ván cờ này hay không. Cậu ấy tìm đến bạn, người giỏi về chiến thuật và phân tích, hy vọng bạn có thể giúp cậu ấy xác định xem có tồn tại chiến thuật nào để giành chiến thắng trong vòng $10^4$ nước đi hay không. Nếu tồn tại chiến thuật chiến thắng như vậy, hãy in ra các thao tác cho từng bước.
Dữ liệu vào
Dữ liệu vào gồm $10$ dòng, mỗi dòng chứa một xâu có độ dài $9$, biểu thị tình trạng bàn cờ. Trong đó ký tự . biểu thị vị trí trống; ký tự C biểu thị quân Xe của ta; ký tự M biểu thị quân Mã của ta; và ký tự S biểu thị Slime của địch.
Mỗi loại ký tự có thể xuất hiện nhiều lần. Dữ liệu đảm bảo có ít nhất một Slime trên bàn cờ và ít nhất một quân đồng minh.
Dữ liệu ra
Nếu không có chiến thuật nào để thắng trong vòng $10^4$ nước đi:
- Hãy in ra một dòng chứa xâu
WuJie.
Nếu tồn tại chiến thuật để thắng trong vòng $10^4$ nước đi:
- Trước tiên, in ra một dòng chứa xâu
YouJie. - Tiếp theo, in ra một số nguyên $s$, biểu thị số lượng hành động.
- Sau đó, in ra $s$ dòng, mỗi dòng chứa bốn số nguyên $a, b, c, d$, cho biết quân đồng minh hiện đang ở $(a, b)$ được di chuyển đến vị trí $(c, d)$. Cụ thể, nếu cả hai vị trí $(a, b)$ và $(c, d)$ đều đã có quân đồng minh, hành động này được coi là Hoán Đổi Hình Dạng, cho biết hai quân cờ này đổi chỗ cho nhau.
- Chiến thuật của bạn phải đảm bảo rằng sau khi hoàn tất mọi hành động, không còn Slime nào trên bàn cờ.
Nếu có nhiều lời giải hợp lệ khác nhau, có thể in ra bất kỳ lời giải nào.
Các lời giải không đáp ứng yêu cầu định dạng, không tuân thủ quy tắc di chuyển quân cờ, hoặc chỉ ra vị trí $(a, b)$ không có quân cờ đều sẽ bị coi là sai.
Ví dụ
Dữ liệu vào 1
...CSC... ...CCCM.. ......... ......... ......... ......... ......... ......... ......... .........
Dữ liệu ra 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
Dữ liệu vào 2
SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSCSSSS
Dữ liệu ra 2
WuJie
Ghi chú
Kết quả đầu ra của ví dụ $1$ minh họa nhiều thao tác hợp lệ và cuối cùng ăn hết tất cả Slime.
- Các bước từ $1$ đến $3$ cho thấy quân Xe tại $(1, 4)$ di chuyển sang trái, chọn đi từng ô một và cuối cùng dừng tại $(1, 1)$.
- Bước $4$ minh họa thao tác Hoán Đổi Hình Dạng, đổi chỗ quân Xe tại $(1, 1)$ với quân Xe tại $(2, 4)$.
- Bước $5$ cho thấy quân Xe tại $(2, 4)$ di chuyển lên $(1, 4)$.
- Bước cuối cùng cho thấy quân Mã nhảy từ $(2, 7)$ đến $(1, 5)$ để ăn Slime duy nhất. Vì không còn vị trí trống hợp lệ nào kề với Slime sau nước đi này nên nó không thể phân tách. Trò chơi giành chiến thắng.