$10$행 $9$열의 체스판 위에서 "기문장기(Qi Men Xiang Qi)"라는 게임이 진행되고 있습니다. 양측은 각각 여러 개의 기물을 가지고 있으며, 서로 다른 기물은 서로 다른 특성을 가집니다. 체스판의 $x$번째 행과 $y$번째 열의 위치를 나타내기 위해 $(x, y)$ 좌표를 사용합니다.
아군은 여러 개의 차(Rook)와 여러 개의 마(Knight), 그리고 기술 "이형환위(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\}$는 순서 없는 집합을 나타냅니다. 이는 전통 체스 나이트의 "L"자 모양 이동에 해당합니다(단, 이 문제에서는 장기처럼 다른 기물이 길을 막는 규칙이 없습니다).
- 이형환위: 한 번의 행동으로 사용하여 임의의 두 아군 기물의 위치를 서로 바꿀 수 있습니다. 사용 횟수에는 제한이 없습니다.
적군은 여러 마리의 슬라임(Slime)을 가지고 있습니다. 슬라임은 이동할 수 없지만 다음과 같은 특성을 가집니다:
- 슬라임이 좌표 $(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)$로 뛰어올라 유일한 슬라임을 잡는 것을 보여줍니다. 이후 슬라임에 인접한 유효한 빈 위치가 없으므로 슬라임은 분열할 수 없습니다. 게임에서 승리합니다.