En la Escuela Solaris ha estallado un incendio que se expande rápidamente por los pasillos. El edificio está representado como una cuadrícula de \(n \times m\) celdas.

Cada celda contiene uno de los siguientes caracteres:

• S — posición inicial del estudiante
• F — celda en llamas
• E — salida
• . — pasillo libre
• # — muro que bloquea el paso

El fuego se propaga en \(4\) direcciones: horizontal y vertical (no diagonalmente). El estudiante puede moverse en \(8\) direcciones: horizontal, vertical y diagonalmente. Cada movimiento consume exactamente \(1\) unidad de tiempo.

Se sabe que el fuego se propaga antes que el estudiante en cada unidad de tiempo. El estudiante no puede entrar en una celda donde ya haya fuego o donde el fuego llegue en ese mismo instante.

Tu tarea es determinar el tiempo mínimo necesario para que el estudiante alcance alguna salida \(E\) antes de ser alcanzado por el fuego.

Input

La primera línea contiene dos enteros \(n\) y \(m\) (\(1 \le n, m \le 2000\)).

Las siguientes \(n\) líneas contienen exactamente \(m\) caracteres cada una, describiendo el mapa de la escuela.

Se garantiza que existe exactamente un \(S\), al menos un \(E\), y cero o más celdas \(F\).

Output

Imprime un único entero:

• El tiempo mínimo para alcanzar una salida, o
• -1 si es imposible escapar.

Ejemplos

Entrada

6 7
.......
..F....
.......
.S...#.
.......
.....E.

Salida

4

Entrada

5 5
#####
#S..#
#.F.#
#..E#
#####

Salida

-1