Description

You are evaluating construction plans for a giant airplane hangar. The hangar floor can be represented as an $n \times n$ grid, where each cell is either empty or contains an obstacle. Rows are numbered from $1$ to $n$ from top to bottom, and columns are numbered from $1$ to $n$ from left to right.

It is important that large containers for storing airplane parts can move freely on the floor. Each container can be seen as an axis-aligned square centered at some cell. For an odd integer $k$, a container of size $k$ is a square covering $k$ rows and $k$ columns. The coordinate of a container is the coordinate of its center cell. A container can move up, down, left, or right, but it cannot touch obstacles and cannot move outside the hangar boundary.

Given $q$ pairs of cells $A_k$ and $B_k$, for each pair, find the maximum size (also an odd integer) of a container that can move from $A_k$ to $B_k$.

Input Format

The first line contains a positive integer $n$ ($2 \le n \le 1000$), the size of the hangar.

The next $n$ lines each contain $n$ characters describing the hangar, where . denotes an empty cell and # denotes an obstacle.

The next line contains a positive integer $q$ ($1 \le q \le 300000$), the number of queries.

Each of the next $q$ lines contains four positive integers $A_x, A_y, B_x, B_y$ ($1 \le A_x, A_y, B_x, B_y \le n$), the coordinates of $A$ and $B$.

It is guaranteed that $A$ and $B$ are distinct empty cells.

Output Format

Output $q$ lines, each with one integer. For each query, output the maximum size. If no solution exists, output $0$.

7
.....#.
...#.#.
....#..
....###
....#..
#......
.......
5
2 5 5 2
2 5 3 6
2 2 6 3
2 2 6 6
1 1 7 7

1
0
3
1
1

Hint

Translated by ChatGPT 5