The wheel to the right

와칠과 토카는 빈칸과 벽만으로 구성된 $1000$행 $1000$열의 격자에 살고 있다.

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

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

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

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

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

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

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

입력은 없다.

첫 번째 줄에 격자의 세로 길이 $N$ $(3 \leq N \leq 1\,000)$와 가로 길이 $M$ $(3 \leq M \leq 1\,000)$를 공백으로 구분하여 출력한다.

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

와칠의 차는 출발지에서 도착지로 유한한 시간 내에 이동 가능해야 한다.

이 문제에서는, 와칠의 차가 출발지에서 도착지까지 이동하는 최단 시간 $T$에 따라 점수가 달라진다. 구체적으로는,

점을 받게 된다. $100$점 이상을 받게 될 경우, 문제를 푼 것(AC) 로 간주된다.

DOJ에 제출 가능한 코드의 최대 길이는 100,000 바이트다.