Mali Danilo treba da se nađe sa svojim najboljim drugom, ali zbog silnih radova u gradu to mu predstavlja problem. Srećom, Danilo uvek nosi par mina sa sobom koje može da iskoristi da stigne do svog druga.

Stanje grada se može opisati matricom, gde je svako polje slobodno ili blokirano radovima. U svakom trenutku Danilo može da pređe sa polja na kom se nalazi na susedna slobodna polja, gde su susedna polja u matrici ona polja koja su neposredno iznad, ispod, levo ili desno od trenutnog polja.

Danilo sme da postavi minu samo na polje koje mu je dostižno. Nakon eksplozije prve mine, pod uslovom da mu je ostalo još mina, Danilo može da postavi sledeću minu na sva polja do koja su mu tada dostižna (moguće je da se skup dostižnih polja proširio nakon eksplozije prve mine).

Ali Danilo je zaboravio snagu svojih mina. Pomozite mu da nađe minimalnu snagu mina ~K~ koja mu je potrebna da bi stigao do svog druga.

Snaga mina određuje veličinu njene eksplozije. Mina snage ~K~ oslobađa sva polja u pravougaoniku veličine ~(2K + 1) * (2K + 1)~, sa centrom u istom polju gde je mina postavljena. Na primer, ako se postavi mina u sredini leve matrice snage ~K = 1~, polja koja je eksplozija obuhvatila su označena sa O i ta polja će na dalje biti prohodna.

X....      X....
XXXXX      XOOOX
X..X. ---> XOOO.
...X.      .OOO.
XX..X      XX..X

Nađi minimalnu potrebnu snagu mina, ~K~, da bi bilo moguće da Danilo postavi mine na neki način tako da stigne do svog druga.

Opis ulaza

U prvom redu nalaze se dva broja ~N~, koji predstavlja dužine stranice matrice, i ~M~, broj mina koji je Danilo poneo sa sobom. Marednih ~N~ redova predstavlja stanje grada. Slobodna polja su označena karakterom . , a blokirana polja sa X. Danilo se nalazi na polju označenim sa A, a njegov drug na polju označenim sa B. Ta dva polja su slobodna.

Opis izlaza

Ispisati prirodan broj ~K~ koji predstavlja minimalnu jačinu mina potrebnu da Danilo stigne do njegovog druga. Ako nije potrebno koristiti mine uopšte, ispisati ~-1~.

Primer 1

Ulaz

6 1
A.XX..
..XX..
XXXX..
..XX..
..XX..
..XX.B

Izlaz

2

Primer 2

Ulaz

7 2
AXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXB

Izlaz

3

Objašnjenje primera

U prvom primeru, Danilo može da postavi minu na polje ~(2, 2)~ ili ~(2, 1)~ jačine ~K=2~ da bi napravio put do svog druga.

U drugom primeru, Danilo može samo da stavi minu na svoju poziciju. Stanje matrice nakon prve eksplozije minom snage ~K=3~ na polje ~(1, 1)~:

....XXX
....XXX
....XXX
....XXX
XXXXXXX
XXXXXXX
XXXXXXB

Sad Danilo jedino može da postavi svoju poslednju minu na polje ~(4, 4)~ da bi otvorio put do svog druga.

Ograničenja

• ~2 \le N \le 500~
• ~1 \le M \le 2~

Postoje tri podzadatka:

• Podzadatak 1 [31 poen]: ~M = 1~.
• Podzadatak 2 [32 poena]: ~N \le 50~.
• Podzadatak 3 [37 poena]: Nema dodatnih ograničenja.

Napomena

Danilo i njegov drug su otporni na eksplozije.