Se dă o matrice cu $n$ linii și $m$ coloane umplută cu trei tipuri de valori:

1. pătrate goale, marcate cu .
2. ziduri, marcate cu #
3. personaje, marcate cu $R$

Cerința problemei este una simplă, trebuie să se afle valoarea maximă a lui $k$ astfel încât dacă extindem zidurile cu $k$ pătrate în toate direcțiile, toate personajele notate cu $R$ pot în continuare să ajungă unii la alții. Se garanteaza ca personajele pot ajunge unii la altii inca de la inceput.

Un personaj se poate deplasa pe matrice în cele $4$ direcții (sus, jos, stânga, dreapta).

O extindere cu $k$ constă în următoarea operație: Pentru fiecare pătrat din matricea inițială marcat cu #, vom marca toate pătratele aflate la distanță cel mult $k$ de ele cu #. Cu alte cuvinte, toate pătratele aflate la distanță cel mult $k$ de un zid din matricea inițială devin și ele ziduri.

Dacă un caracter este blocat de un zid din cauza extinderii cu $x$, atunci nu putem extinde zidul cu $x$.

Se garantează ca există cel puțin un zid în fiecare test și cel puțin două personaje.

Date de intrare

Pe prima linie a fișierului de intrare expansion.in se găsesc două numere întregi, $n$ și $m$.

Următoarele $n$ linii vor conține descrierea matricii, care are $n$ linii și $m$ coloane și conține caracterele menționate mai sus, $a_{i, j}$ reprezentând pătratul de pe linia $i$ și coloana $j$.

Date de ieșire

Pe prima linie a fișierului de ieșire expansion.out se va găsi un singur număr întreg, valoarea lui $k$, conform descrierii din enunt.

Restricții și precizări

• $1 \leq n, m \leq 2 \cdot 10^3$;

Exemplul 1

expansion.in

5 5
R...R
.....
..#..
.....
R...R

expansion.out

1

Explicație

Cu roșu am notat zidurile inițiale și cu portocaliu, zidurile obținute ca urmare a extinderilor.

Pentru primul exemplu, toate $R$-urile pot ajunge unul la altul dacă extindem zidurile cu $1$, dar acest lucru va fi imposibil dacă am extinde zidurile cu $2$.

Exemplul 2

expansion.in

2 6
R#.#.R
......

expansion.out

0

Explicație

Pentru al doilea exemplu, dacă am extinde zidurile cu $1$ pătrat, $R$-ul din ($1, 1$) ar fi prins între ziduri.