Snowflakes

Interview

Time limit1sMemory limit1024 MB

Summary

Given a grid of snowflake characters, find the largest size, where each snowflake's size is the shortest arm among its eight directions from the center.

Level: Easy3 of 10
Topics: Matrix, Implementation, Brute force
Solved: No attempts yet

Problem

Lana likes to draw specific snowflakes. A snowflake of size $x$ is defined as follows:

The center of the snowflake is the character +.
Above and below the character + there is a sequence of $x$ characters |.
To the left and right of the character + there is a sequence of $x$ characters -.
On the diagonal from the upper left corner to the center and from the center to the lower right corner of the snowflake there is a sequence of $x$ characters \.
On the diagonal from the upper right corner to the center and from the center to the lower left corner of the snowflake there is a sequence of $x$ characters /.

The figures below show a snowflake of size 1, two connected snowflakes of sizes 2 and 1, and a snowflake of size 1 that is missing one | to be of size 2.

\|/
-+-
/|\

\.|./..
.\|/...
--+--..
./|\...
/.|.\|/
....-+-
..../|\

\.|./.
.\|/..
--+---
./|\..
/...\.

Lana is currently drawing snowflakes on a piece of paper of size $n \times m$ . Some snowflakes are missing characters, so the size of such a snowflake is the smallest length of its character sequence from the center in any of the eight directions. The drawing may also contain characters that are not part of any snowflake.

Regardless of whether snowflakes share characters, the size of each one is determined separately. Find the size of the largest snowflake in the drawing.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 50$ ), the size of the drawing.

Each of the following $n$ lines contains $m$ characters describing the drawing. The drawing uses only the characters +, -, \, |, /, and ..

Output

Print the size of the largest snowflake in the drawing on a single line.

Hint

In the first example, only one snowflake is drawn. In the up-left, up, and up-right directions from its center, the sequences have length 1. In the right and down-right directions, they have length 2. In the left, down-left, and down directions, they have length 3. The smallest length is 1, so the size is 1.

In the second example, two connected snowflakes are drawn. The left one has size 2, and the right one has size 1.

Examples3

Example 1

Input

5 6
\.\|/.
---+--
/./|\.
./.|.\
/..|..

Expected output

Example 2

Input

7 7
\.|./..
.\|/...
--+--..
./|\...
/.|.\|/
....-+-
..../|\

Expected output

Example 3

Input

7 7
\|/|\|/
-+-|-+-
/|\|/|\
---+---
\|/|\|/
-+-|-+-
/|\|/|\

Expected output