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.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static StringTokenizer tokenizer;
	static int[] xOff = {0, 0, 1, -1};
	static int[] yOff = {1, -1, 0, 0};
	public static void main(String[] args) throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
		int n = nextInt();
		int m = nextInt();
		boolean[][] black = new boolean[n][m];
		Queue<Integer> rQ = new ArrayDeque<Integer>();
		Queue<Integer> cQ = new ArrayDeque<Integer>();
		int curr = 0, next = 0, ans = 0;
		for(int i = 0; i < n; i++) {
			String t = next();
			for(int k = 0; k < m; k++) {
				black[i][k] = t.charAt(k) == '#';
				if(black[i][k]) {
					curr++;
					rQ.add(i);
					cQ.add(k);
				}
			}
		}
		while(!rQ.isEmpty()) {
			if(curr == 0) {
				curr = next;
				next = 0;
				ans++;
			}
			curr--;
			int r = rQ.poll();
			int c = cQ.poll();
			for(int i = 0; i < 4; i++) {
				if(r + xOff[i] >= 0 && r + xOff[i] < n && c + yOff[i] >= 0 && c + yOff[i] < m && !black[r + xOff[i]][c + yOff[i]]) {
					next++;
					black[r + xOff[i]][c + yOff[i]] = true;
					rQ.add(r + xOff[i]);
					cQ.add(c + yOff[i]);
				}
			}
		}
		System.out.println(ans);

	}

	public static String next() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			String line = br.readLine();
			if (line == null)
				throw new IOException();
			tokenizer = new StringTokenizer(line);
		}
		return tokenizer.nextToken();
	}

	public static int nextInt() throws IOException {
		return Integer.parseInt(next());
	}

	public static long nextLong() throws IOException {
		return Long.parseLong(next());
	}

	public static double nextDouble() throws IOException {
		return Double.parseDouble(next());
	}
}