이 문제는 인터랙티브 문제입니다.
Taja는 이 게임을 쉽게 이길 수 있지만, 그녀의 친구들은 그렇지 못했습니다. 이제 그녀가 당신에게 이 게임을 제안합니다.
게임 장비는 $n \times n$ ($5 \le n \le 40$) 크기의 필드, 말, 두 개의 동전(COIN1, COIN2), 방위가 적힌 두 개의 주사위(DICE1, DICE2), 그리고 한 칸 크기의 블록들로 구성됩니다.
| 이름 | 면의 개수 | 면 |
|---|---|---|
| COIN1. 이동 동전 | 2 | SLIDE, RAM |
| COIN2. 수정 동전 | 2 | PLACE, REMOVE |
| DICE1. 방향 주사위 1 | 4 | N (북), S (남), W (서), E (동) |
| DICE2. 방향 주사위 2 | 8 | N (북), S (남), W (서), E (동), NW (북서), NE (북동), SW (남서), SE (남동) |
게임이 시작되기 전에 말과 일부 블록들이 필드 위에 배치됩니다. 그 후 플레이어는 다음과 같은 방식으로 이동합니다. 먼저 플레이어는 동전 하나를 선택하여 던져서 행동을 결정합니다. 그 다음 주사위 하나를 선택하여 굴려 방향 $dir$을 결정합니다. 그 후 다음 네 가지 행동 중 하나가 일어납니다.
| 행동 | 설명 |
|---|---|
| SLIDE | 말이 블록이나 미로 경계에 부딪힐 때까지 $dir$ 방향의 빈 칸을 따라 이동합니다. |
| RAM | 말이 첫 번째 블록에 부딪힐 때까지 $dir$ 방향의 빈 칸을 따라 이동합니다. 그 후 말과 블록을 같은 방향으로 밀어, 움직이는 블록이 다른 블록이나 필드 경계에 부딪힐 때까지 이동합니다. |
| PLACE | 말의 $dir$ 방향으로 인접한 칸이 비어 있고 필드 내부라면, 해당 칸에 블록을 놓습니다. |
| REMOVE | 말의 $dir$ 방향으로 인접한 칸에 블록이 있고 필드 내부라면, 해당 칸에서 블록을 제거합니다. |
목표는 말을 도착 칸에 놓는 것입니다. 이 문제에서 하나의 쿼리는 동전 던지기 한 번과 주사위 굴리기 한 번을 의미합니다.
인터랙션 프로토콜
먼저 인터랙터가 미로의 크기, 미로의 상태, 그리고 도착 칸의 좌표를 제공합니다. 그 후 다음 4단계의 행동이 일어납니다.
- 심판 프로그램이 말의 좌표를 출력하거나 말이 도착 칸에 도달했음을 알립니다.
- 당신의 프로그램이 동전 이름을 출력합니다.
- 심판 프로그램이 동전에 나온 행동 이름을 출력합니다.
- 당신의 프로그램이 주사위 이름을 출력합니다.
- 심판 프로그램이 주사위에 나온 방향 이름과 "RAM" 행동에 대한 추가 정보를 출력합니다.
출력
표준 출력은 동전 이름과 주사위 이름, 두 줄로 구성되어야 합니다. 동전 이름은 "COIN1" 또는 "COIN2"입니다. 주사위 이름은 "DICE1" 또는 "DICE2"입니다. 각 줄을 출력한 후에는 반드시 표준 출력을 비워야(flush) 합니다.
입력
표준 입력의 첫 번째 줄에는 미로의 크기인 정수 $n$이 주어집니다. 다음 $n$개의 줄에는 빈 칸을 나타내는 "." (ASCII 46) 또는 블록이 있는 칸을 나타내는 "#" (ASCII 35) 문자가 $n$개씩 주어집니다. 다음 줄에는 도착 칸의 행 번호와 열 번호인 두 정수 $r_f$와 $c_f$가 주어집니다. 왼쪽 상단 모서리는 $(1, 1)$이고, 오른쪽 하단 모서리는 $(n, n)$입니다. 도착 칸과 초기 칸은 비어 있습니다.
다음 그룹들은 각 이동을 설명합니다.
- 그룹의 첫 번째 줄에는 말의 행 번호와 열 번호인 두 정수 $r, c$가 주어지며, 말이 도착 칸에 도달한 경우 $(-1, -1)$이 주어집니다.
- 다음 줄에는 동전에 나온 행동 이름이 주어집니다.
- 다음 줄에는 주사위에 나온 방향 이름이 주어집니다.
- 현재 행동이 "RAM"인 경우, 다음 두 문자열에는 두 정수 $r_1, c_1$과 $r_2, c_2$가 포함되어 있으며, 이는 말이 좌표 $(r_1, c_1)$에 있는 블록과 충돌하여 해당 블록을 $(r_2, c_2)$ 칸으로 이동시켰음을 의미합니다.
북쪽 방향은 행 번호가 감소하는 방향입니다. 남쪽은 행 번호가 증가하는 방향입니다. 서쪽 방향은 열 번호가 감소하는 열 번호입니다. 동쪽 방향은 열 번호가 증가하는 방향입니다. 동전이나 주사위의 각 면은 동일한 확률로 나옵니다.
예제
입력 1
5 #.... ..... ..... ..... ..#.. 4 3 1 5 PLACE W 1 5 RAM S 6 5 6 5 5 5 RAM W 5 3 5 1 5 2 PLACE NE 5 2 RAM NE 4 3 2 5 3 4 REMOVE NE 3 4 PLACE S 3 4 SLIDE W 3 1 RAM S 5 1 5 1 4 1 SLIDE E -1 -1
출력 1
COIN2 DICE1 COIN1 DICE1 COIN1 DICE1 COIN2 DICE2 COIN1 DICE2 COIN2 DICE2 COIN2 DICE1 COIN1 DICE1 COIN1 DICE1 COIN1 DICE1
참고
예제에 대한 미로의 초기 상태는 다음과 같습니다.
경로에 대한 시각적 표현은 다음과 같습니다.
