브제코슬라브라는 이름의 늑대가 있는데 이 늑대는 피에 굶주린 사냥꾼들로부터 도망치고 있다.
사냥꾼들은 똑똑하고 나무 뒤에 숨어있다.
브제코슬라브는 그것을 알고 있지만 어느 나무인지는 알지 못한다.
따라서 그는 도망치기 위해서 나무들로부터 최대한 멀리 떨어져서 이동하고 싶어한다.
그는 현재 위치로부터 그의 집까지 도망쳐야 한다.

숲은 N*M 모양의 그리드로 표현된다.
빈 초원은 '.' 으로, 나무는 '+' 으로, 브제코슬라브의 현재 위치는 'V' 으로, 그의 집은 'J' 로 표현된다.

브제코슬라브는 북쪽, 동쪽, 남쪽, 서쪽으로 이동할 수 있으며 나무가 있는 곳도 자유롭게 갈 수 있다.

브제코슬라브의 현재 위치가 (R,C) 이고 나무가 (A,B) 이면
브제코슬라브와 나무 사이의 거리는 |R-A|+|C-B| 이다.

그를 도와 최적의 길을 찾아주도록 하자.
최적의 길은 이동하는 중에 나무와의 거리의 최소값이 최대가 되는 길이다.

입력

• 첫번째 줄에는 N 과 M 이 입력된다.
• 다음 줄 부터 숲의 모양이 입력된다.

출력

입출력 예

input

4?4
+...
....
....
V..J

output

3

input

4?5
.....
.+++.
.+.+.
V+.J+

output

0

The forest can be represented as a N by M gird. Let us mark empty meadow patches with '.', patches with a tree in the middle with '+', Vjekoslav's current position with 'V' and the position of his cottage with 'J'. Vjekoslav can run from his current patch to any other patch north, east, south or west from him, even if it contains a tree.

If Vjekoslav is standing in R-th row and C-th column on the grid and there is a tree in the A-th row and B-th column then the distance between Vjekoslav and that tree is:

|R-A| + |C-B|

Help Vjekoslav find the best route to his cottage. The best route is any route that maximizes the minimal distance between Vjekoslav and all trees at any given moment.

Note that Vjekoslav's cottage doesn't occupy the entire patch so that patch must also be included in the route.

입력

• The first line of input contains integers N and M (1 ≤ N, M ≤ 500), grid dimensions.
• The next N lines contain M characters each: '.', '+', 'V', 'J'. Input will contain exactly one character 'V' and 'J' and at least one character '+'.

출력

입출력 예

input

4?4
+...
....
....
V..J

output

3

input

4?5
.....
.+++.
.+.+.
V+.J+

output

0

출처:COCI 2009/2010 contest2 4/6
번역: KangJ