Pada papan catur berukuran $10$ baris kali $9$ kolom, sebuah permainan bernama "Qi Men Xiang Qi" sedang dimainkan. Setiap sisi memiliki beberapa bidak, dan bidak yang berbeda memiliki karakteristik yang berbeda. Kita menggunakan koordinat $(x, y)$ untuk menyatakan posisi pada baris ke-$x$ dan kolom ke-$y$ dari papan catur.
Sisi kita memiliki beberapa Benteng (Rook) dan beberapa Kuda (Knight), serta keahlian Berubah Wujud (Shape-shifting). Metode pergerakan dari kedua jenis bidak ini dan keahliannya dijelaskan sebagai berikut:
- Misalkan Benteng berada di koordinat $(a, b)$. Jika ia bergerak ke koordinat $(c, d)$ di papan catur dalam satu aksi, syarat-syarat berikut harus dipenuhi:
- Tidak ada bidak kawan di $(c, d)$. Artinya, ia tidak dapat memakan bidak kawan, maupun bertumpuk dengan bidak kawan.
- $c = a$ atau $d = b$, tetapi $(a, b) \neq (c, d)$. Artinya, ia dapat bergerak sepanjang baris atau kolom tempat ia berada, tetapi tidak boleh tetap di posisi yang sama.
- Tidak boleh ada bidak lain di antara $(a, b)$ dan $(c, d)$. Artinya, ia tidak dapat melompati bidak lain saat bergerak.
- Misalkan Kuda berada di koordinat $(a, b)$. Jika ia bergerak ke koordinat $(c, d)$ di papan catur dalam satu aksi, syarat-syarat berikut harus dipenuhi:
- Tidak ada bidak kawan di $(c, d)$. Artinya, ia tidak dapat memakan bidak kawan, maupun bertumpuk dengan bidak kawan.
- $\{|a - c|, |b - d|\} = \{1, 2\}$. Di sini, $\{\dots\}$ menyatakan himpunan tak terurut. Ini sesuai dengan gerakan catur tradisional berbentuk huruf "L" (perhatikan bahwa tidak ada "halangan kaki kuda" dalam soal ini).
- Berubah Wujud (Shape-shifting): Ini dapat digunakan sebagai satu aksi untuk menukar posisi dua bidak kawan mana saja. Tidak ada batasan jumlah penggunaan.
Musuh memiliki beberapa Slime. Slime tidak dapat bergerak tetapi memiliki karakteristik berikut:
- Misalkan Slime berada di koordinat $(a, b)$. Ketika ia dimakan dan disingkirkan, ia akan segera membelah diri, menghasilkan satu Slime di masing-masing dari empat posisi yang bersebelahan (atas, bawah, kiri, kanan). Secara khusus, di keempat posisi yang bersebelahan ini, tidak ada slime baru yang akan dihasilkan di posisi yang sudah ditempati bidak lain atau berada di luar batas papan catur.
- Slime yang dihasilkan dari pembelahan diri memiliki karakteristik pembelahan yang sama dan tidak ada batasan jumlah pembelahan.
Setelah menggerakkan bidak, jika bidak tersebut bertumpuk dengan bidak musuh, maka akan memicu pemakanan yang menyingkirkan bidak musuh. Syarat kemenangan permainan ini adalah memakan semua Slime musuh, memastikan tidak ada bidak musuh yang tersisa di papan catur.
Saat memainkan permainan ini, Xiao Biao menemukan bahwa meskipun musuh tidak dapat menggerakkan bidak mereka, tetap sulit bagi sisi kita untuk memakan habis Slime dengan bersih, karena jumlahnya banyak dan membelah diri dengan sangat efisien, sering kali menyebabkan lebih banyak slime yang dihasilkan, sehingga sulit bagi Xiao Biao untuk menentukan apakah kemenangan mungkin dicapai dalam permainan ini. Dia datang kepada Anda, yang ahli dalam strategi dan analisis, berharap Anda dapat membantunya menentukan apakah ada strategi untuk mencapai kemenangan dalam $10^4$ langkah. Jika strategi kemenangan seperti itu ada, keluarkan operasi untuk setiap langkahnya.
Masukan
Masukan terdiri dari $10$ baris, masing-masing berisi sebuah string dengan panjang $9$, yang menyatakan situasi papan catur. Karakter . menyatakan posisi kosong; karakter C menyatakan Benteng kita; karakter M menyatakan Kuda kita; dan karakter S menyatakan Slime musuh.
Setiap jenis karakter dapat muncul beberapa kali. Data menjamin bahwa setidaknya ada satu Slime di papan catur dan setidaknya satu bidak kawan.
Keluaran
Jika tidak ada strategi untuk menang dalam $10^4$ langkah:
- Keluarkan satu baris berisi string
WuJie.
Jika ada strategi untuk menang dalam $10^4$ langkah:
- Pertama, keluarkan satu baris berisi string
YouJie. - Selanjutnya, keluarkan sebuah bilangan bulat $s$, yang menyatakan banyaknya aksi.
- Kemudian, keluarkan $s$ baris, masing-masing berisi empat bilangan bulat $a, b, c, d$, yang menunjukkan bahwa bidak kawan yang saat ini berada di $(a, b)$ dipindahkan ke posisi $(c, d)$. Secara khusus, jika kedua posisi $(a, b)$ dan $(c, d)$ sudah memiliki bidak kawan, aksi ini dianggap sebagai Berubah Wujud, yang menunjukkan bahwa kedua bidak ini bertukar posisi.
- Strategi Anda harus memastikan bahwa setelah semua aksi selesai, tidak ada Slime yang tersisa di papan catur.
Jika terdapat beberapa solusi valid yang berbeda, keluarkan salah satu saja.
Solusi yang tidak memenuhi persyaratan format, tidak mematuhi aturan pergerakan bidak, atau menunjuk posisi $(a, b)$ yang tidak memiliki bidak akan dianggap salah.
Contoh
Masukan 1
...CSC... ...CCCM.. ......... ......... ......... ......... ......... ......... ......... .........
Keluaran 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
Masukan 2
SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSCSSSS
Keluaran 2
WuJie
Catatan
Keluaran untuk contoh $1$ menunjukkan beberapa operasi yang valid, dan pada akhirnya memakan semua slime.
- Langkah $1$ hingga $3$ menunjukkan Benteng di $(1, 4)$ bergerak ke kiri, memilih untuk bergerak satu petak setiap kali, dan akhirnya mendarat di $(1, 1)$.
- Langkah $4$ menunjukkan operasi Berubah Wujud, menukar Benteng di $(1, 1)$ dengan Benteng di $(2, 4)$.
- Langkah $5$ menunjukkan Benteng di $(2, 4)$ bergerak ke atas menuju $(1, 4)$.
- Langkah terakhir menunjukkan Kuda melompat dari $(2, 7)$ ke $(1, 5)$ untuk memakan satu-satunya Slime. Karena tidak ada posisi kosong yang valid di sebelah Slime setelah langkah ini, ia tidak dapat membelah diri. Permainan dimenangkan.