Grid Perigoso

Time limit: 1000 msMemory limit: 256 MB

Você recebe uma grade de tamanho $N \times M$ que contém células vazias, células perigosas, uma célula inicial $S$ e uma célula de destino $T$ .

O nível de segurança de uma célula $(x, y)$ é a menor distância de Manhattan entre essa célula e qualquer célula perigosa. A distância de Manhattan entre duas células $(x_1, y_1)$ e $(x_2, y_2)$ é definida como

|x_1 - x_2| + |y_1 - y_2|.

O nível de segurança de um caminho é o menor nível de segurança entre todas as células visitadas pelo caminho, incluindo as células $S$ e $T$ .

Você pode se mover de uma célula para outra célula adjacente para cima, para baixo, para a esquerda ou para a direita, sem sair dos limites da grade. Todas as células podem ser atravessadas, inclusive as células perigosas.

Encontre o maior nível de segurança possível entre todos os caminhos de $S$

Input

A primeira linha contém dois inteiros $N$ e $M$ ( $1 \le N, M \le 1000$ ; $N \cdot M \ge 3$ ) — o número de linhas e de colunas da grade, respectivamente.

Output

Imprima um único inteiro — o maior nível de segurança possível de um caminho de $S$ até $T$ .

Samples

Sample 1

Input

4 4
S...
.D..
..D.
...T

Output

Por exemplo, podemos seguir o caminho

$(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (1,4)\rightarrow (2,4) \rightarrow (3,4) \rightarrow (4,4).$

Grid Perigoso

Input

Output

Samples

Sample 1

Submit

Submissions