Maximum Odd Container Movement in Aircraft Warehouse

You are given an aircraft warehouse modeled as an \(n\times n\) grid. Each cell is either empty or contains an obstacle. Rows are numbered from 1 to \(n\) (top to bottom) and columns from 1 to \(n\) (left to right).

A large container used for storing airplane parts is represented as a square with odd side length \(k\). The container is centered at some cell \((r,c)\) and occupies a \(k\times k\) block; that is, if \(d = \frac{k-1}{2}\), the container covers all cells in the rectangle from \((r-d, c-d)\) to \((r+d, c+d)\). The container may move up, down, left or right one cell at a time. However, during its movement, it must always remain completely inside the grid and must not cover any obstacles.

You are given \(q\) queries. Each query consists of two grid cells \(A = (r_A, c_A)\) and \(B = (r_B, c_B)\). For each query, determine the maximum odd integer \(k\) such that a container of size \(k\) can be moved from cell \(A\) to cell \(B\) following the rules described above.

Note that a container of size \(k\) can only be placed if its entire \(k\times k\) area is within the grid and free of obstacles. In other words, for a container centered at \((r, c)\), it is only valid if \(r-d \ge 1\), \(r+d \le n\), \(c-d \ge 1\), \(c+d \le n\) and the region contains no obstacles.

Your task is to answer each query by finding the maximum odd \(k\) for which there exists a valid path from \(A\) to \(B\) using only valid positions for the container.

inputFormat

The first line contains two integers \(n\) and \(q\) \( (1 \le n \le 1000,\ 1 \le q \le 10^5)\) representing the size of the grid and the number of queries, respectively.

The next \(n\) lines each contain a string of length \(n\) consisting of characters '.' (empty cell) and '#' (obstacle), describing the grid.

Each of the next \(q\) lines contains four integers \(r_A\), \(c_A\), \(r_B\), \(c_B\) \( (1 \le r_A, c_A, r_B, c_B \le n)\) representing the starting cell and destination cell for a query.

outputFormat

For each query, output a single line with an integer representing the maximum odd integer \(k\) such that a container of size \(k\) can be moved from \(A\) to \(B\). If no container with size at least 1 can be moved, output 0.

sample

5 2
.....
..#..
.....
.#...
.....
1 1 5 5
2 2 4 4

1
1