31944번 - 스시스시 아일랜드 스페셜 저지

문제

SCSC의 트레저 헌터 종환이는 안타깝게도 고물을 주우며 삶을 연명하고 있었다. 그러던 어느 날, 종환이는 우연히 보물이 잔뜩 묻힌 보물섬이 존재한다는 정보를 입수했다. 그곳은 바로 스시스시 아일랜드. 천금 같은 기회를 놓치고 싶지 않았던 종환이는 가지고 있는 장비를 모두 챙겨 모험을 떠났다. 종환이는 우여곡절 끝에 보물이 있는 곳까지 도달했지만 안타깝게도 엄청난 난관에 봉착하고 말았다······. 보물을 지키는 스시스시 아일랜드의 스호자가 종환이에게 시련을 준 것이다.

"스시스시의 힘이 담긴 특별한 석판이 있다. 석판 위에 한쪽 면에만 표식이 있는 돌을 정사각형 모양으로 나열해 두었다. 석판 위의 돌들을 뒤집어 내가 제시한 모양대로 만든다면 이 섬의 보물은 모두 네 것이다. 단, 이 석판은 매우 특별하기 때문에 몇 가지 제약이 있다.

• 돌을 한 번 뒤집을 때마다 S 또는 C 모양으로 뒤집어야 한다. S 또는 C가 회전한 모양으로 돌을 뒤집을 수 있다.
• S 또는 C 모양으로 돌을 뒤집는 횟수는 석판 위에 놓인 돌의 개수보다 작거나 같아야 한다.

할 수 있겠는가?"

스시스시 아일랜드의 보물을 가져갈 수 있도록 종환이를 도와주자!

입력

첫째 줄에 석판의 크기 $N$이 주어진다. $(16 \leq N \leq 30)$

둘째 줄부터 $N$개의 줄에 걸쳐 스호자가 제시한 돌의 모양이 주어진다. $i$번째 행, $j$번째 열에 위치한 문자는 $(i, j)$에 위치한 돌의 모양을 나타내며 X는 표식이 있는 면, .은 표식이 없는 면을 의미한다. $(0 \leq i , j \lt N)$

출력

석판 위의 돌은 초기에 모두 표식이 없는 면이 위에 오도록 놓여 있다. 돌을 뒤집는 동작을 다음 두 가지 형식을 이용하여 출력한다.

• S $r$ $x$ $y$ : $(x, y)$를 중심으로 하고 $r \times 90^{\circ}$ 만큼 시계방향으로 회전한 S 모양에 위치한 돌을 뒤집는다.
• C $r$ $x$ $y$ : $(x, y)$를 중심으로 하고 $r \times 90^{\circ}$ 만큼 시계방향으로 회전한 C 모양에 위치한 돌을 뒤집는다. $(0 \leq r < 4;$ 0ドル \leq x < N;$ 0ドル \leq y < N)$

석판 위의 돌은 가장 왼쪽에서 가장 위에 있는 돌을 $(0, 0)$으로 할 때 아래쪽을 $x$값이 증가하는 방향, 오른쪽을 $y$값이 증가하는 방향으로 하여 좌표로 나타낼 수 있다. 가장 오른쪽에서 가장 아래에 있는 돌의 좌표가 $(N-1, N-1)$이다.

S 또는 C 모양은 각각 다음과 같이 5ドル \times 3$ 또는 3ドル \times 5$ 격자에 색칠된 모양이다. 주어진 모양을 90ドル^{\circ}$ 간격으로 회전시킬 수는 있지만 뒤집는 것은 불가능하다. 모양의 중심은 아래 그림의 O 표시가 있는 지점이다. 격자의 가장 왼쪽에서 가장 위에 있는 지점을 $(0, 0)$이라 할 때 해당 모양이 5ドル \times 3$ 크기에 들어오는 경우 $(2, 1)$에 위치한 지점, 3ドル \times 5$에 들어오는 경우 $(1, 2)$에 위치한 지점을 의미한다.

모양 전체가 석판 안에 있어야 함에 유의하자. S 또는 C 모양에 위치한 모든 돌을 뒤집어야 한다.

출력한 동작을 따라 석판 위의 돌을 뒤집었을 때 스호자가 제시한 모양과 같아진다면 맞았습니다!!를 받는다.

석판의 조건에 따라 최대 $N^{2}$번까지만 동작을 출력할 수 있다. 그보다 많은 횟수를 출력할 경우 예상치 못한 채점 결과를 받을 수 있다.

제한

노트

어떤 입력이 주어져도 주어진 횟수 내에 제시된 모양을 만들 수 있다. 제시된 모양을 만드는 방법은 유일하지 않을 수 있다.