Statement
와칠과 토카는 빈칸과 벽만으로 구성된 행 열의 격자에 살고 있다.
와칠은 바퀴가 고장나 우회전만 가능한 차에 타고 있다. 와칠은 차를 타고 출발지에서 도착지까지 이동하려고 한다. 와칠의 차는 다음 두 가지 방법으로만 이동할 수 있고 격자 외부로는 이동할 수 없다.
- 보고 있는 방향의 오른쪽 칸이 빈칸이면 오른쪽 방향으로 회전하고 그 칸으로 이동할 수 있다.
- 보고 있는 방향의 앞쪽 칸이 빈칸이면 그 칸으로 이동할 수 있다.
두 가지 이동 방법 모두 초가 걸린다.
격자 조작 능력을 가진 토카는 와칠의 고장난 차를 보고 와칠이 출발지에서 목적지까지 가는 데 걸리는 시간을 매우 길게 만들면 재미있겠다고 생각했다.
토카는 와칠이 출발하기 전 다음과 같이 격자를 조작할 수 있다. 토카의 격자 조작 능력은 일회용이기 때문에 격자를 한 번 조작하면 격자를 다시 조작할 수 없다.
- 격자를 행 열()의 빈칸만 있는 격자로 변경한다.
- 칸 이상 칸 이하의 빈칸을 벽으로 변경한다.
- 격자의 빈칸 중 원하는 두 개의 칸을 각각 출발지와 도착지로 지정한다.
와칠의 차가 출발지에서 도착지까지 이동하는 데 걸리는 시간을 매우 길게 만들어 보자. 와칠의 차는 처음에 오른쪽을 보고 있다.
Input
입력은 없다.
Output
첫 번째 줄에 격자의 세로 길이 와 가로 길이 를 공백으로 구분하여 출력한다.
두 번째 줄부터 줄에 걸쳐 개의 문자로 토카가 조작한 격자를 출력한다. 빈칸은 ., 벽은 #, 출발지는 S, 도착지는 F로 나타낸다. 출발지와 도착지는 격자 내에 유일하게 존재해야 하며, .로 나타내지 않더라도 빈칸임에 유의하라.
와칠의 차는 출발지에서 도착지로 유한한 시간 내에 이동 가능해야 한다.
Scoring
이 문제에서는, 와칠의 차가 출발지에서 도착지까지 이동하는 최단 시간 에 따라 점수가 달라진다. 구체적으로는,
점을 받게 된다. 점 이상을 받게 될 경우, 문제를 푼 것(AC) 로 간주된다.
Note
DOJ에 제출 가능한 코드의 최대 길이는 100,000 바이트다.