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.PrintWriter;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.Scanner;
public class Main  implements Runnable { 

    public static void main(String[] args) {
        new Thread(null, new Main(), "", 16 * 1024 * 1024).start(); 
    }

    public void run() {
    	Scanner sc = new Scanner(System.in);
/*		FastScanner sc = new FastScanner("6 6 \r\n" +
				"..#..#\r\n" +
				"......\r\n" +
				"#..#..\r\n" +
				"......\r\n" +
				".#....\r\n" +
				"....#.");*/
		int h = Integer.parseInt(sc.next());
		int w = Integer.parseInt(sc.next());
		//int b = Integer.parseInt(sc.next());
		//int t = Integer.parseInt(sc.next());
		//int k = 0;
		//int k = Integer.parseInt(sc.next());
		//String str = sc.next();
		//char c[] = str.toCharArray();
		char a[][] = new char[h][w];
		int atmp[] = new int[h];
		int max= 0;
		int blackar[][] = new int[h*w][2];
		int p=0;
		for (int i = 0; i < h; i++)
		{
				a[i]= sc.next().toCharArray();
				for (char j = 0; j < w; j++)
				{
					if(a[i][j]=='#')
					{
						blackar[p][0]=i;
						blackar[p][1]=j;
						p++;
					}
				}
		}

		int maxp = p;
    	int p2=p;
		p=0;
	    while(p<h*w)
	    {
		    int hap = 0;
			for (; p<maxp;p++)
			{
				int i = blackar[p][0];
				int j = blackar[p][1];
				//if(a[i][j] == '.')
				//{
					if(i-1>=0)
					{
						if (a[i-1][j] == '.')
						{
							a[i-1][j] = '#';
							blackar[p2][0]=i-1;
							blackar[p2][1]=j;
							p2++;
						}
					}
					if(j-1>=0)
					{
						if (a[i][j-1] == '.')
						{
							a[i][j-1] = '#';
							blackar[p2][0]=i;
							blackar[p2][1]=j-1;
							p2++;
						}
					}
					if(i+1<h)
					{
						if (a[i+1][j] == '.')
						{
							a[i+1][j] = '#';
							blackar[p2][0]=i+1;
							blackar[p2][1]=j;
							p2++;
						}
					}
					if(j+1<w)
					{
						if (a[i][j+1] == '.')
						{
							a[i][j+1] = '#';
							blackar[p2][0]=i;
							blackar[p2][1]=j+1;
							p2++;
						}
					}
				//}

		    }
			maxp=p2;
			max++;

		}
	    max= max-1;

		int ans = max;

		PrintWriter out = new PrintWriter(System.out);
		out.println(ans);
		out.flush();
	}

    static class FastScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;
        public FastScanner(String in) {
        	StringReader sr = new StringReader(in);
            reader = new BufferedReader(new BufferedReader(sr));
            tokenizer = null;
        }
        public FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        public String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return tokenizer.nextToken("\n");
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
        
        public long nextInt() {
            return Integer.parseInt(next());
        }

    }

}