미로 챌린지

이 문제는 투 스텝 + 인터렉티브 문제입니다. 첫 번째 실행, 두 번째 실행을 꼼꼼히 읽어 문제를 파악하시기를 바랍니다.

---

피돌이는 최근 유행하는 '미로 챌린지'에 도전하기로 했다. 이 챌린지는 $N \times N$ 크기의 격자 형태로 이루어진 미로에서 진행되며 미로의 각 칸은 빈칸, 벽, 또는 목적지이다. 챌린지의 목표는 임의의 빈칸에서 출발해 목적지에 도달하는 것이다. 단, 미로의 전체 구조는 미리 알 수 없으며, 피돌이는 현재 위치와 지나온 경로에 대한 것만을 알 수 있다.

피돌이는 목적지에 도달하기 위해 현재 위치에서 상하좌우 중 한 방향을 골라 그 방향으로 한 칸 움직이는 이동을 시도할 수 있다. 만약 이동하려는 칸이 벽이거나 격자 밖으로 벗어나게 되는 칸이라면 위치는 변하지 않지만, 그렇지 않은 경우 선택한 방향으로 한 칸 이동한다. 목적지에 도달할 때까지 이를 반복한다.

또한 같은 칸은 최대 2번 밟을 수 있다. 구체적으로, 초기에 모든 빈칸의 내구도는 2이며 어떤 빈칸에서 이동을 시도하면 그 빈칸의 내구도가 1 감소한다. 벽에 막히거나 격자 밖으로 벗어나게 되어 위치가 변하지 않은 경우에도 내구도가 1 감소한다. 만약 피돌이가 내구도가 0인 칸에 위치하게 된다면 즉시 실패하게 된다.

챌린지가 너무 어렵다고 느낀 피돌이는 당신에게 도움을 요청했다. 당신은 피돌이의 초기 위치를 알 수는 없지만 미로의 구조를 확인할 수 있으며 피돌이가 미로에 들어가기 전에 미리 미로의 빈칸 몇 개를 골라 그 위에 돌멩이를 놓을 수 있다. 이 과정에서 빈칸의 내구도가 변화하지는 않는다. 당신이 놓은 돌멩이들은 피돌이의 이동에는 영향을 못 미치지만, 피돌이는 자신이 있는 칸에 당신이 배치한 돌멩이가 있는지 알 수 있다. 즉, 피돌이는 당신이 놓은 돌멩이를 목적지에 도달하기 위한 힌트로 삼을 수 있다.

피돌이와 당신은 미리 전략을 논의할 수 있지만, 당신이 미로의 구조를 확인한 후에는 더 이상 서로 대화할 수 없다. 피돌이가 챌린지에 성공할 수 있도록 피돌이를 도와주자.

이 문제는 두 번 실행되며 첫 번째 실행에서는 당신의 전략을, 두 번째 실행에서는 피돌이의 전략을 구현해야 한다.

첫 번째 줄에는 몇 번째 실행인지 나타내는 정수 $T$가 주어진다. $(T\in \\{1,2 \\})$

$T=1$인 경우 첫 번째 실행을 나타낸다.

1. 첫째 줄에 격자의 크기를 나타내는 정수 $N$이 주어지고 다음 $N$줄에 격자를 나타내는 문자열이 주어진다. $i+1$번째 줄의 $j$번째 문자는 격자의 $i$행 $j$열을 나타낸다. .는 빈칸, #는 벽, G는 목적지를 나타낸다. 단, 목적지는 단 하나 있으며 피돌이가 어떤 빈칸에서 시작하더라도 목적지까지 가는 경로가 있음이 보장된다. $(2 \leq N \leq 100)$
2. 이 중 빈칸을 몇 개 골라 돌멩이를 배치한 후 $N$줄에 걸쳐 격자를 출력한다. 이때 돌멩이를 배치한 칸은 S로 나타낸다. 빈칸 외에는 돌멩이를 배치할 수 없으며 돌멩이를 배치하지 않은 칸은 모두 주어진 격자와 같아야 한다.

$T=2$인 경우 두 번째 실행을 나타낸다.

1. 첫째 줄에 피돌이의 초기위치에 대한 정보를 나타내는 세 정수 $y$, $x$, $k$가 공백으로 구분되어 주어진다. $y$와 $x$는 현재 위치가 $y$행 $x$열에 있는 칸임을 나타내고 $k$는 현재 칸의 돌멩이의 유무를 나타낸다. $k=1$이면 현재 칸에 돌멩이가 있음을 나타내고 $k=0$이면 현재 칸에 돌멩이가 없음을 나타낸다. $(1\leq y,x \leq N; k\in \\{0,1\\})$
2. 피돌이가 이동을 시도할 방향을 출력한다. 이동 방향은 U, D, L, R로 나타내며 각각 위, 아래, 왼쪽, 오른쪽을 나타낸다. 선택한 방향으로 한 칸 이동을 시도한 후 도착한 칸에 대한 정보가 $y$, $x$, $k$의 꼴로 초기위치와 비슷하게 주어진다. 단, 이동 방향을 출력한 후 표준 출력 버퍼를 flush해 주어야 한다. 그렇지 않으면 예상치 못한 결과를 받을 수 있다. 언어별로 표준 출력 버퍼를 flush하는 방법은 노트를 참고하라.
3. 만약 도착한 칸이 목적지라면 칸에 대한 정보 대신 0 0 0이 출력되고 프로그램이 종료된다. 만약 도착한 칸을 이미 2번 이상 지났다면 -1 -1 -1이 출력되고 틀렸습니다를 받게 된다. 둘 다 아니라면 2. 로 되돌아가 반복한다.

언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.

• C: fflush(stdout)
• C++: std::cout « std::flush
• Java: System.out.flush()
• Python: sys.stdout.flush()
• Kotlin: System.out.flush()