Мали Данило треба да се нађе са својим најбољим другом, али због силних радова у граду то му представља проблем. Срећом, Данило увек носи пар мина са собом које може да искористи да стигне до свог друга.

Стање града се може описати матрицом, где је свако поље слободно или блокирано радовима. У сваком тренутку Данило може да пређе са поља на ком се налази на суседна слободна поља, где су суседна поља у матрици она поља која су непосредно изнад, испод, лево или десно од тренутног поља.

Данило сме да постави мину само на поље које му је достижно. Након експлозије прве мине, под условом да му је остало још мина, Данило може да постави следећу мину на сва поља до која су му тада достижна (могуће је да се скуп достижних поља проширио након експлозије прве мине).

Али Данило је заборавио снагу својих мина. Помозите му да нађе минималну снагу мина \(К\) која му је потребна да би стигао до свог друга.

Снага мина одређује величину њене експлозије. Мина снаге \(K\) ослобађа сва поља у правоугаонику величине \((2K+1)*(2K+1)\), са центром у истом пољу где је мина постављена.

На пример, ако се постави мина у средини леве матрице снаге \(K = 1\), поља која је експлозија обухватила су означена са O и та поља ће на даље бити проходна.

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

Нађи минималну потребну снагу мина, \(K\), да би било могуће да Данило постави мине на неки начин тако да стигне до свог друга.

Опис улаза

У првом реду налазе се два броја \(N\), који представља дужине странице матрице, и \(M\), број мина који је Данило понео са собом. Nаредних \(N​\) редова представља стање града.

Слободна поља су означена карактером . , а блокирана поља са X. Данило се налази на пољу означеним са A, а његов друг на пољу означеним са B. Та два поља су слободна.

Опис излаза

Исписати природан број \(K\) који представља минималну јачину мина потребну да Данило стигне до његовог друга. Ако није потребно користити мине уопште, исписати -1.

Пример 1

Улаз

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

Излаз

2

Пример 2

Улаз

7 2
AXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXX
XXXXXXB

Излаз

3

Објашњење примера

У првом примеру, Данило може да постави мину на поље \((2,2)\) или \((2,1)\) јачине \(K = 2\) да би направио пут до свог друга.

У другом примеру, Данило може само да стави мину на своју позицију. Стање матрице након прве експлозије мином снаге \(K = 3\) на поље \((1,1)\):

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

Сад Данило једино може да постави своју последњу мину на поље \((4,4)\) да би отворио пут до свог друга.

Ограничења

• \(2 \leq N \leq 500\)
• \(1 \leq M \leq 2\)

Постоје три подзадатка:

• Подзадатак 1 [31 поена]: \(M = 1\).
• Подзадатак 2 [32 поена]: \(N \leq 50\).
• Подзадатак 3 [37 поена]: Нема додатних ограничења.

Напомена

Данило и његов друг су отпорни на експлозије.