Problem: You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black. HW characters from A_{11} to A_{HW} represent the colors of the squares. A_{ij} is `#` if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is `.` if that square is white.

We will repeatedly perform the following operation until all the squares are black:

* Every white square that shares a side with a black square, becomes black.



Find the number of operations that will be performed. The initial grid has at least one black square.

Constraints

* 1 \leq H,W \leq 1000
* A_{ij} is `#` or `.`.
* The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:


H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}


Output

Print the number of operations that will be performed.

Examples

Input

3 3
...
.#.
...


Output

2


Input

6 6
..#..#
......
..#..
......
.#....
....#.


Output

3

Solution (in JAVA):

Solution:
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		char[][] A = new char[H][W];
		Queue<int[]> queue = new ArrayDeque<int[]>();
		for (int i=0;i<H;i++) {
			String row=sc.next();
			for (int j=0;j<W;j++) {
				A[i][j]=row.charAt(j);
				if (A[i][j]=='#') {
					int[] start = {i,j,0};
					queue.add(start);
				}
			}
		}

		int[][] flag = new int[H][W];
		int ans=0;
		//DFS
		int[] dx = {1,-1,0,0};
		int[] dy = {0,0,1,-1};
		loop:while (!queue.isEmpty()) {
			int[] temp=queue.remove();
			int y=temp[0];
			int x=temp[1];
			int depth=temp[2];
			for (int i=0;i<4;i++) {
				if (0<=y+dy[i] && y+dy[i]<=H-1 && 0<=x+dx[i] && x+dx[i]<=W-1) {
					if (flag[y+dy[i]][x+dx[i]]==0 && A[y+dy[i]][x+dx[i]]=='.') {
						flag[y+dy[i]][x+dx[i]]=1;
						int[] queue_add={y+dy[i],x+dx[i],depth+1};
						queue.add(queue_add);
						ans=depth+1;
					}
				}
			}
		}
		System.out.println(ans);
	}
}