Поплавите се чуден феномен. Особено оние кое се случуваат во академските институции во Македонија.

За жал, затвореникот Роби кој се наоѓа во некој затвор далеку од Скопје и е јунакот на оваа приказна ја немал таа можност (да се префрла од еден во друг дел на затворот на чуден начин). Тој, за да се ослободи од затворот морал најрегуларно да помине преку слободните ходници од истиот. Во нормални услови не би можел ни чекор да направи бидејќи затворот бил полн со чувари, но по тревогата за можна поплава сите тие избегале. Сега тој треба да го најде најдобриот можен начин да излезе од затворот.

Информации за затворот ни се дадени на влез како правоаголна матрица, во која со 'R' е означен елементот каде што се наоѓа Роби, со '.' се означени позициите каде што Роби може да се движи, со '*' се означени ѕидовите, а со 'Z' е означен излезот од затворот. Роби може да се движи од еден кон друг елемент во матрицата ако тој елемент е слободен и соседен (се наоѓа лево, десно, горе или долу од дадениот).

Уште повеќе, бидејќи Роби не е во најдобри односи со останатите затвореници, тој сака да помине што е можно подалеку од секој од нив (затворениците се означени со 'G') , т.е. секогаш не интересира колку било најмалото растојание до некој затвореник на патот по кој тој стигнал до излезот (вклучувајќи ги и почетната и крајната позиција). Најдобар би бил оној пат каде таквото најмало растојание е максимално (најголемо можно). Растојанието од Роби до друг затвореник се дефинира како чекорите кои му се потребни на Роби за да стигне до тој затвореник.

Влез

Во прв ред се наоѓаат два цели броеви N и M (1 <= N, M <= 1000), кои ги означуваат бројот на редици и бројот на колони од матрицата, соодветно. Во секој од следните N редови, се наоѓаат по M знаци кои ја опишуваат матрицата (според описот даден погоре).

Излез

Еден број – бројот кој ја претставува максималната вредност на минималното растојание до еден затвореник. Секогаш ќе има пат од 'R' до 'Z'.

Ограничувања

Временско ограничување: 2 seconds
Мемориско ограничување: 64 megabytes

Примери

влез
8 9
.R.......
.........
..G...G..
.........
G........
....G....
...**....
...Z.....

излез
2

Објаснување: Еве едно можно решение:

.R+++....
....+....
..G.+.G..
....++...
G....+++.
....G..+.
...**..+.
...Z++++.