$10$ 行 $9$ 列のチェス盤上で、「奇門象棋」と呼ばれるゲームが行われています。双方にいくつかの駒があり、異なる駒は異なる特徴を持っています。チェス盤の $x$ 行目、$y$ 列目の位置を表すために座標 $(x, y)$ を使用します。
味方にはいくつかの「車」（Rook）といくつかの「馬」（Knight）、およびスキル「移形換位」（Shape-shifting）があります。これら 2 種類の駒の移動方法とスキルの説明は以下の通りです：
- 「車」が座標 $(a, b)$ にあるとします。1 回の行動でチェス盤上の座標 $(c, d)$ に移動する場合、以下の条件を満たす必要があります：
- $(c, d)$ に味方の駒がないこと。つまり、味方の駒を取ることはできず、味方の駒と重なることもできません。
- $c = a$ または $d = b$ であり、かつ $(a, b) \neq (c, d)$ であること。つまり、同じ行または同じ列に沿って移動できますが、同じ位置に留まることはできません。
- $(a, b)$ と $(c, d)$ の間に他の駒が一切ないこと。つまり、移動中に他の駒を飛び越えることはできません。
- 「馬」が座標 $(a, b)$ にあるとします。1 回の行動でチェス盤上の座標 $(c, d)$ に移動する場合、以下の条件を満たす必要があります：
- $(c, d)$ に味方の駒がないこと。つまり、味方の駒を取ることはできず、味方の駒と重なることもできません。
- $\{|a - c|, |b - d|\} = \{1, 2\}$ であること。ここで $\{\dots\}$ は順序なし集合を表します。これは伝統的なチェスのナイトの「L」字型の移動に対応します（なお、この問題には中国象棋の「蹩馬脚（馬の足止め）」のルールはありません）。
- 移形換位：1 回の行動として使用でき、任意の 2 つの味方の駒の位置を入れ替えます。使用回数に制限はありません。
敵にはいくつかの「スライム」（Slime）がいます。スライムは移動できませんが、以下の特徴を持っています：
- スライムが座標 $(a, b)$ にあるとします。スライムが取られて盤上から取り除かれると、即座に分裂し、隣接する 4 つの位置（上、下、左、右）にそれぞれ 1 体のスライムを生成します。具体的には、これら 4 つの隣接位置のうち、すでに他の駒が存在する位置や盤外の位置には新しいスライムは生成されません。
- 分裂によって生成されたスライムも同じ分裂特性を持ち、分裂の回数に制限はありません。
駒を移動させた後、敵の駒と重なった場合は捕獲が発生し、敵の駒が取り除かれます。ゲームの勝利条件は、敵のスライムをすべて捕獲し、チェス盤上に敵の駒が 1 つも残っていない状態にすることです。
ゲームをプレイしているうちに、小標は、敵が駒を動かせないにもかかわらず、スライムの数が多く非常に効率的に分裂してさらに多くのスライムが生成されることが多いため、味方がスライムをきれいに全滅させるのは難しく、このゲームで勝利が可能かどうかを判断するのが難しいことに気づきました。彼は戦略と分析に長けたあなたのところへやって来て、$10^4$ 手以内に勝利を収める戦略が存在するかどうかを判定する手助けをしてほしいと願っています。そのような必勝戦略が存在する場合は、各ステップの操作を出力してください。
入力
入力は $10$ 行からなり、各行にはチェス盤の状況を表す長さ $9$ の文字列が含まれます。文字 . は空きマスを表し、文字 C は味方の「車」を表し、文字 M は味方の「馬」を表し、文字 S は敵の「スライム」を表します。
各種類の文字は複数回現れることがあります。データにより、チェス盤上に少なくとも 1 体のスライムと少なくとも 1 つの味方の駒が存在することが保証されます。
出力
$10^4$ 手以内に勝つ戦略が存在しない場合：
- 1 行の文字列
WuJieを出力してください。
$10^4$ 手以内に勝つ戦略が存在する場合：
- まず、1 行の文字列
YouJieを出力してください。 - 次に、行動の回数を表す整数 $s$ を出力してください。
- 続いて $s$ 行を出力してください。各行には 4 つの整数 $a, b, c, d$ を含め、現在 $(a, b)$ にある味方の駒を位置 $(c, d)$ に移動させることを表します。特に、位置 $(a, b)$ と $(c, d)$ の両方にすでに味方の駒がある場合、この行動は「移形換位」とみなされ、これら 2 つの駒の位置を入れ替えることを表します。
- あなたの戦略は、すべての行動が完了した後にチェス盤上にスライムが残っていないことを保証しなければなりません。
有効な解が複数存在する場合は、そのうちのどれを出力しても構いません。
フォーマット要件を満たさない解、駒の移動ルールに従わない解、または位置 $(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, 1)$ に到達します。
- ステップ $4$ では、「移形換位」操作によって $(1, 1)$ の「車」と $(2, 4)$ の「車」を入れ替えます。
- ステップ $5$ では、$(2, 4)$ の「車」が上の $(1, 4)$ に移動します。
- 最後のステップでは、「馬」が $(2, 7)$ から $(1, 5)$ に跳んで唯一のスライムを捕獲します。この後、スライムに隣接する有効な空きマスが存在しないため、スライムは分裂できません。ゲームに勝利します。