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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Objects;

public class Main {
    public static void main(String[] args) {
        Out out = new Out();
        solve(out);
        out.outln();
        out.flush();
        out.close();
    }

    public static void solve(Out out) {
        int h = In.ni();
        int w = In.ni();
        boolean[][] g = In.inputGrid(h, w, '#');
        IntDeque dq = new IntDeque();
        int[] d = new int[h * w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (g[i][j]) {
                    dq.addLast(i * w + j);
                    d[i * w + j] = 0;
                } else {
                    d[i * w + j] = -1;
                }
            }
        }
        int max = 0;
        while (dq.nonEmpty()) {
            int ij = dq.pollFirst();
            int i = ij / w;
            int j = ij % w;
            for (int dir = 0; dir < 4; dir++) {
                int y = i + Const.dy[dir];
                int x = j + Const.dx[dir];
                int yx = y * w + x;
                if (Range.in(0, y, h) && Range.in(0, x, w) && d[yx] < 0) {
                    d[yx] = d[ij] + 1;
                    max = Math.max(max, d[yx]);
                    dq.addLast(yx);
                }
            }
        }
        out.append(max);
    }
}


class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
            ptr++;
        }
        return hasNextByte();
    }

    public String next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
            throw new NumberFormatException();
        }
        return (int) nl;
    }

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


class Range implements Comparable<Range> {
    private static final Range EMPTY = new Range(0, 0);

    public long l;
    public long r;

    public Range(long l, long r) {
        if (r <= l) {
            this.l = 0;
            this.r = 0;
        } else {
            this.l = l;
            this.r = Math.max(l, r);
        }
    }

    public Range(long r) {
        this(0, r);
    }

    public long length() {
        return r - l;
    }

    public boolean contains(long v) {
        return in(l, v, r);
    }

    public boolean contains(Range r) {
        return contains(this.l, this.r, r.l, r.r);
    }

    public boolean crosses(Range r) {
        return crosses(this.l, this.r, r.l, r.r);
    }

    public Range crossRange(Range r) {
        if (crosses(r)) {
            return new Range(Math.max(this.l, r.l), Math.min(this.r, r.r));
        } else {
            return EMPTY;
        }
    }
    
    /**
     * this is a DESTRUCTIVE method. receive a list of {@code Range} and unite them.
     * including some {@code Iterator.remove()}, requires being LinkedList.
     * @param list LinkedList.
     * @param sorted if the list is already sorted.
     */
    public static void unionRange(LinkedList<Range> list, boolean sorted) {
        if (!sorted) {
            Collections.sort(list);
        }
        Iterator<Range> iter = list.iterator();
        if (iter.hasNext()) {
            Range now = iter.next();
            while (iter.hasNext()) {
                Range r = iter.next();
                if (now.crosses(r)) {
                    now.r = Math.max(now.r, r.r);
                    iter.remove();
                } else {
                    now = r;
                }
            }
        }
    }

    /**
     * this is a DESTRUCTIVE method. receive a list of {@code Range} and unite them.
     * including some {@code Iterator.remove()}, requires being LinkedList.
     * @param list (unsorted) LinkedList.
     */
    public static void unionRange(LinkedList<Range> list) {
        unionRange(list, false);
    }

    /**
     * this is a DESTRUCTIVE method. receive a list of {@code Range}, unite them, and calculate the sum of length.
     * including some {@code Iterator.remove()}, requires being LinkedList.
     * @param list LinkedList.
     * @param sorted if the list is already sorted.
     * @return sum of length of Ranges.
     */
    public static long lengthSum(LinkedList<Range> list, boolean sorted) {
        unionRange(list, sorted);
        long ret = 0;
        for (Range r : list) {
            ret += r.length();
        }
        return ret;
    }

    /**
     * this is a DESTRUCTIVE method. receive a list of {@code Range}, unite them, and calculate the sum of length.
     * including some {@code Iterator.remove()}, requires being LinkedList.
     * @param list (unsorted) LinkedList.
     * @return sum of length of Ranges.
     */
    public static long lengthSum(LinkedList<Range> list) {
        return lengthSum(list, false);
    }

    /**
     * judge value is in [l, r).
     * @param l closed.
     * @param value evaluated value.
     * @param r open.
     * @return value is in [l, r)
     */
    public static boolean in(long l, long value, long r) {
        return l <= value && value < r;
    }

    /**
     * judge value is out of [l, r). (i.e. value is in (-infty, l) or [r, infty))
     * @param l closed.
     * @param value evaluated value.
     * @param r open.
     * @return value is out of [l, r) (i.e. value is in (-infty, l) or [r, infty))
     */
    public static boolean outOf(long l, long value, long r) {
        return !in(l, value, r);
    }

    public static boolean crosses(long l1, long r1, long l2, long r2) {
        return l1 < r2 && l2 < r1;
    }

    public static boolean contains(long l1, long r1, long l2, long r2) {
        return l1 <= l2 && r2 <= r1;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        } else if (!(o instanceof Range)) {
            return false;
        } else {
            Range r = (Range) o;
            return this.l == r.l && this.r == r.r;
        }
    }

    @Override
    public int hashCode() {
        return Objects.hash(l, r);
    }

    @Override
    public String toString() {
        return "[" + l + ", " + r + ")";
    }

    @Override
    public int compareTo(Range r) {
        return Long.compare(this.l, r.l);
    }
}


class Out {
    private StringBuilder sb = new StringBuilder();
    private PrintWriter w = new PrintWriter(System.out);

    public Out() {
    }

    public void append(int v) {
        sb.append(v);
    }

    public void append(int[] a, String sep) {
        for (int i = 0; i < a.length; i++) {
            append(a[i]);
            if (i < a.length - 1) {
                append(sep);
            }
        }
    }

    public void append(int[] a, char sep) {
        append(a, String.valueOf(sep));
    }

    public void append(int[] a) {
        append(a, "\n");
    }

    public void append(long v) {
        sb.append(v);
    }

    public void append(long[] a, String sep) {
        for (int i = 0; i < a.length; i++) {
            append(a[i]);
            if (i < a.length - 1) {
                append(sep);
            }
        }
    }

    public void append(long[] a, char sep) {
        append(a, String.valueOf(sep));
    }

    public void append(long[] a) {
        append(a, "\n");
    }

    public void append(double v) {
        sb.append(v);
    }

    public void append(double[] a, String sep) {
        for (int i = 0; i < a.length; i++) {
            append(a[i]);
            if (i < a.length - 1) {
                append(sep);
            }
        }
    }

    public void append(double[] a, char sep) {
        append(a, String.valueOf(sep));
    }

    public void append(double[] a) {
        append(a, "\n");
    }

    public void append(char c) {
        sb.append(c);
    }

    public void append(char[] c) {
        sb.append(c);
    }

    public void append(char[][] c) {
        for (char[] e : c) {
            append(e);
            append('\n');
        }
    }

    public void append(String[] a, String sep) {
        for (int i = 0; i < a.length; i++) {
            append(a[i]);
            if (i < a.length - 1) {
                append(sep);
            }
        }
    }

    public void append(String[] a, char sep) {
        append(a, String.valueOf(sep));
    }

    public void append(String[] a) {
        append(a, "\n");
    }

    public void append(Object e) {
        sb.append(e);
    }

    public void append(Object[] a, String sep) {
        for (int i = 0; i < a.length; i++) {
            append(a[i]);
            if (i < a.length - 1) {
                append(sep);
            }
        }
    }

    public void append(Object[] a, char sep) {
        append(a, String.valueOf(sep));
    }

    public void append(Object[] a) {
        append(a, "\n");
    }

    public void out() {
        w.print(sb);
        clearBuilder();
    }

    public void outln() {
        w.println(sb);
        clearBuilder();
    }

    // public void print(String s) {
    //     w.print(s);
    // }

    // public void println() {
    //     w.println();
    // }

    // public void println(int v) {
    //     w.println(v);
    // }

    // public void println(long v) {
    //     w.println(v);
    // }

    // public void println(double v) {
    //     w.println(v);
    // }

    // public void println(char c) {
    //     w.println(c);
    // }

    // public void println(String s) {
    //     w.println(s);
    // }

    // public void println(Object e) {
    //     w.println(e);
    // }

    // public void println(String sep, int... a) {
    //     StringBuilder s = new StringBuilder();
    //     for (int i = 0; i < a.length; i++) {
    //         s.append(a[i]);
    //         if (i < a.length - 1) {
    //             s.append(sep);
    //         }
    //     }
    //     println(s.toString());
    // }

    // public void println(char sep, int... a) {
    //     println(String.valueOf(sep), a);
    // }

    // public void println(String sep, long... a) {
    //     StringBuilder s = new StringBuilder();
    //     for (int i = 0; i < a.length; i++) {
    //         s.append(a[i]);
    //         if (i < a.length - 1) {
    //             s.append(sep);
    //         }
    //     }
    //     println(s.toString());
    // }

    // public void println(char sep, long... a) {
    //     println(String.valueOf(sep), a);
    // }

    // public void println(String sep, double... a) {
    //     StringBuilder s = new StringBuilder();
    //     for (int i = 0; i < a.length; i++) {
    //         s.append(a[i]);
    //         if (i < a.length - 1) {
    //             s.append(sep);
    //         }
    //     }
    //     println(s.toString());
    // }

    // public void println(char sep, double... a) {
    //     println(String.valueOf(sep), a);
    // }

    // public void println(String sep, String... a) {
    //     StringBuilder s = new StringBuilder();
    //     for (int i = 0; i < a.length; i++) {
    //         s.append(a[i]);
    //         if (i < a.length - 1) {
    //             s.append(sep);
    //         }
    //     }
    //     println(s.toString());
    // }

    // public void println(char sep, String... a) {
    //     println(String.valueOf(sep), a);
    // }

    // public void println(String sep, Object... a) {
    //     StringBuilder s = new StringBuilder();
    //     for (int i = 0; i < a.length; i++) {
    //         s.append(a[i]);
    //         if (i < a.length - 1) {
    //             s.append(sep);
    //         }
    //     }
    //     println(s.toString());
    // }

    // public void println(char sep, Object... a) {
    //     println(String.valueOf(sep), a);
    // }

    public void flush() {
        w.flush();
    }

    public void close() {
        w.close();
    }

    public void clearBuilder() {
        sb = new StringBuilder();
    }

    public void reverse() {
        sb.reverse();
    }

    public void delete(int start, int end) {
        sb.delete(start, end);
    }

    public void delete(int length) {
        sb.delete(sb.length() - length, sb.length());
    }

    public int length() {
        return sb.length();
    }
}

class IntDeque {
    private int head = -1;
    private int tail = 0;
    private int pSize;
    private int nSize;
    private int p[];
    private int n[];

    public IntDeque(int initialSize) {
        this.nSize = initialSize / 2;
        this.pSize = initialSize - this.nSize;
        this.p = new int[this.pSize];
        this.n = new int[this.nSize];
    }

    public IntDeque() {
        this(64);
    }

    public void addLast(int v) {
        putByRawIndex(tail++, v);
    }

    public void addFirst(int v) {
        putByRawIndex(head--, v);
    }

    public int pollFirst() {
        if (size() == 0) {
            System.err.println("Error in IntDeque::pollFirst. cannot poll element from \"EMPTY\" IntDeque.");
        }
        return getByRawIndex(++head);
    }

    public int pollLast() {
        if (size() == 0) {
            System.err.println("Error in IntDeque::pollLast. cannot poll element from \"EMPTY\" IntDeque.");
        }
        return getByRawIndex(--tail);
    }

    public int get(int index) {
        index += head + 1;
        if (index >= tail) {
            System.err.println("Error in IntDeque::get(" + index + "). the size of IntDeque is " + size() + ".");
        }
        return getByRawIndex(index);
    }

    public int size() {
        return tail - head - 1;
    }

    private void reSize(boolean positive) {
        if (positive) {
            int[] pCopy = new int[pSize << 1];
            System.arraycopy(p, 0, pCopy, 0, pSize);
            p = pCopy;
            pSize <<= 1;
        } else {
            int[] nCopy = new int[nSize << 1];
            System.arraycopy(n, 0, nCopy, 0, nSize);
            n = nCopy;
            nSize <<= 1;
        }
    }

    private int getByRawIndex(int index) {
        if (index >= 0) {
            return p[index];
        } else {
            return n[-(index + 1)];
        }
    }

    private void putByRawIndex(int index, int v) {
        if (index < 0) {
            if (index <= -(nSize + 1)) {
                reSize(false);
            }
            n[-(index + 1)] = v;
        } else {
            if (index >= pSize) {
                reSize(true);
            }
            p[index] = v;
        }
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public boolean nonEmpty() {
        return size() != 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (int i = 0; i < size(); i++) {
            sb.append(get(i));
            if (i < size() - 1) {
                sb.append(", ");
            }
        }
        sb.append(']');
        return sb.toString();
    }
}

class Const {
    public static final long MOD7 = 1_000_000_007;
    public static final long MOD9 = 1_000_000_009;
    public static final long MOD99 = 998_244_353;

    public static final long LINF = 1_000_000_000_000_000_000l;
    public static final int IINF = 1_000_000_000;
    public static final double DINF = 1e150;

    public static final double DELTA = 0.000_000_000_1;
    public static final double LDELTA = 0.000_001;

    public static final String YES = "YES";
    public static final String NO = "NO";
    public static final String Yes = "Yes";
    public static final String No = "No";
    public static final String POSSIBLE = "POSSIBLE";
    public static final String IMPOSSIBLE = "IMPOSSIBLE";
    public static final String Possible = "Possible";
    public static final String Impossible = "Impossible";

    public static final int[] dx8 = {1, 0, -1, 0, 1, -1, -1, 1};
    public static final int[] dy8 = {0, 1, 0, -1, 1, 1, -1, -1};
    public static final int[] dx = {1, 0, -1, 0};
    public static final int[] dy = {0, 1, 0, -1};

    public static long MOD = MOD7;

    public static void setMod(long mod) {
        MOD = mod;
    }

    private Const(){}
}


class In {
    public static final FastScanner fsc = new FastScanner();

    public static int ni() {
        return fsc.nextInt();
    }

    public static int[] ni(int n) {
        int[] a = new int[n];
        Arrays.setAll(a, i -> fsc.nextInt());
        return a;
    }

    public static int[][] ni(int n, int m) {
        int[][] a = new int[n][m];
        Arrays.setAll(a, i -> ni(m));
        return a;
    }

    public static long nl() {
        return fsc.nextLong();
    }

    public static long[] nl(int n) {
        long[] a = new long[n];
        Arrays.setAll(a, i -> fsc.nextLong());
        return a;
    }

    public static long[][] nl(int n, int m) {
        long[][] a = new long[n][m];
        Arrays.setAll(a, i -> nl(m));
        return a;
    }

    public static double nd() {
        return fsc.nextDouble();
    }

    public static double[] nd(int n) {
        double[] a = new double[n];
        Arrays.setAll(a, i -> nd());
        return a;
    }

    public static double[][] nd(int n, int m) {
        double[][] a = new double[n][m];
        Arrays.setAll(a, i -> nd(m));
        return a;
    }

    public static String ns() {
        return fsc.next();
    }

    public static String[] ns(int n) {
        String[] s = new String[n];
        Arrays.setAll(s, i -> ns());
        return s;
    }

    public static char[] nc() {
        return fsc.next().toCharArray();
    }

    public static char[][] nc(int n, int m) {
        char[][] c = new char[n][m];
        Arrays.setAll(c, i -> nc());
        return c;
    }

    public static boolean[][] inputGrid(int h, int w, char truechar) {
        boolean[][] grid = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            char[] s = fsc.next().toCharArray();
            for (int j = 0; j < w; j++) {
                grid[i][j] = s[j] == truechar;
            }
        }
        return grid;
    }
}