Milkweed Invasion

Farmer John’s pasture is represented as a rectilinear grid with width \(X\) and height \(Y\) (\(1 \le X, Y \le 100\)). The lower left corner has coordinates \((1,1)\). The pasture consists of grassy cells, denoted by a dot ('.'), and rocky cells (boulders), denoted by an asterisk ('*').

At time zero, milkweed starts growing at cell \((M_x,M_y)\) (which is guaranteed to be a grassy cell). Each week, the milkweed spreads from any infected cell to all of its 8 neighboring cells (adjacent horizontally, vertically, and diagonally) that are not rocky. Once a cell is invaded by milkweed, it remains invaded. The process continues until all grassy cells are taken over.

Your task is to determine after how many weeks the milkweed completely invades the pasture.

The pasture is described by \(Y\) lines of \(X\) characters each, provided in top-to-bottom order. Note that the coordinate \((1,1)\) refers to the bottom-left cell.

Input Format (detailed below):

• The first line contains two integers: \(X\) and \(Y\).
• The second line contains two integers: \(M_x\) and \(M_y\), the coordinates of the initial milkweed cell.
• The next \(Y\) lines each consist of \(X\) characters, representing the pasture. The first of these lines is the top row (row \(Y\)) and the last is the bottom row (row 1).

Output Format: Output a single integer representing the number of weeks required for the milkweed to invade every grassy cell in the field.

inputFormat

The input consists of:

1. A line with two integers \(X\) and \(Y\), the width and height of the pasture.
2. A line with two integers \(M_x\) and \(M_y\), the starting coordinates of the milkweed.
3. \(Y\) lines each containing a string of length \(X\) representing the pasture grid. The first line corresponds to the top row, and the last line corresponds to the bottom row. Grassy cells are denoted by '.' and rocky cells by '*'.

outputFormat

Output a single integer: the number of weeks required for the milkweed to completely invade all grassy cells.

sample

4 3
1 1
....
..*.
.**.

4