35000번 - The wheel to the right 스페셜 저지

문제

와칠과 토카는 빈칸과 벽만으로 구성된 1ドル,000円$행 1ドル,000円$열의 격자에 살고 있다.

와칠은 바퀴가 고장나 우회전만 가능한 차에 타고 있다. 와칠은 차를 타고 출발지에서 도착지까지 이동하려고 한다. 와칠의 차는 다음 두 가지 방법으로만 이동할 수 있고 격자 외부로는 이동할 수 없다.

• 보고 있는 방향의 오른쪽 칸이 빈칸이면 오른쪽 방향으로 회전하고 그 칸으로 이동할 수 있다.
• 보고 있는 방향의 앞쪽 칸이 빈칸이면 그 칸으로 이동할 수 있다.

두 가지 이동 방법 모두 1ドル$초가 걸린다.

격자 조작 능력을 가진 토카는 와칠의 고장난 차를 보고 와칠이 출발지에서 목적지까지 가는 데 걸리는 시간을 매우 길게 만들면 재미있겠다고 생각했다.

토카는 와칠이 출발하기 전 다음과 같이 격자를 조작할 수 있다. 토카의 격자 조작 능력은 일회용이기 때문에 격자를 한 번 조작하면 격자를 다시 조작할 수 없다.

• 격자를 $N$행 $M$열 $(3 \le N, M \le 1,000円)$의 빈칸만 있는 격자로 변경한다.
• 0ドル$칸 이상 $N \times M - 2$칸 이하의 빈칸을 벽으로 변경한다.
• 격자의 빈칸 중 원하는 두 개의 칸을 각각 출발지와 도착지로 지정한다.

와칠의 차가 출발지에서 도착지까지 이동하는 데 걸리는 시간을 매우 길게 만들어 보자. 와칠의 차는 처음에 오른쪽을 보고 있다.

입력

입력은 없다.

출력

첫 번째 줄에 조작한 격자의 행의 개수 $N$ $(3 \leq N \leq 1,000円)$과 열의 개수 $M$ $(3 \leq M \leq 1,000円)$을 공백으로 구분하여 출력한다.

두 번째 줄부터 $N$줄에 걸쳐 $M$개의 문자로 토카가 조작한 격자를 출력한다. 빈칸은 ., 벽은 #, 출발지는 S, 도착지는 F로 나타낸다. 출발지와 도착지는 격자 내에 유일하게 존재해야 하며, .로 나타내지 않더라도 빈칸임에 유의하라.

와칠의 차는 출발지에서 도착지로 유한한 시간 내에 이동 가능해야 하며, 어떻게 이동하더라도 이동하는 데 소요되는 시간이 최소 $\mathbf{1,300円,000円}$초 이상이어야 한다.

제한

노트

위의 모든 예제는 출력 형식을 지키지만 정답이 아니다.