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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Main{
	static Queue<Integer> Q;
	static int H,W;
	static int[] xv= {1,0,-1,0};
	static int[] yv= {0,1,0,-1};
	static int[][] ary;
	public static void main(String[] args) {
		SC sc=new SC(System.in);
		H=sc.nextInt();
		W=sc.nextInt();
		String[] s=new String[H];
		for(int i=0; i<H; i++) {
			s[i]=sc.next();
		}
		ary=new int[H][W];
		Q=new ArrayDeque<Integer>();
		for(int i=0; i<H; i++) {
			for(int j=0; j<W; j++) {
				if(s[i].charAt(j)=='#') {
					ary[i][j]=0;
					Q.add(i*W+j);
				}
				else {
					ary[i][j]=114514;
				}
			}
		}
		while(!Q.isEmpty()) {
			int now=Q.poll();
			isvalid(now);
		}
		int max=0;
		for(int i=0; i<H; i++) {
			for(int j=0; j<W; j++) {
				max=Math.max(max, ary[i][j]);
			}
		}
		/*for(int i=0; i<H; i++) {
			for(int j=0; j<W; j++) {
				p(ary[i][j]+" ");
			}
			pl("");
		}*/
		pl(max);
	}
	public static void isvalid(int num) {
		int y=num/W;
		int x=num%W;
		for(int i=0; i<4; i++) {
			if(y+yv[i]>=0 && y+yv[i]<H) {
				if(x+xv[i]>=0 && x+xv[i]<W) {
					if(ary[y+yv[i]][x+xv[i]]>2000) {
						Q.add((y+yv[i])*W+(x+xv[i]));
						ary[y+yv[i]][x+xv[i]]=ary[y][x]+1;
					}
				}
			}
		}
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
		}
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void p(Object o) {
		System.out.print(o);
	}
}