You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你正在评估一些关于一个巨型飞机仓库的建设计划。飞机仓库的地面可以表示为 $n$ 行 $n$ 列的网格图，其中每个格子要么是空的，要么有障碍物。行从上到下依次被编号为 $1$ 到 $n$，列从左到右依次被编号为 $1$ 到 $n$。

存放飞机零件的大型集装箱能在飞机仓库的地面上自由移动是很重要的。我们可以将每个集装箱看作一个以某个格子为中心的边平行于坐标轴的正方形。对于一个奇数 $k$，一个尺寸为 $k$ 的集装箱是一个包含 $k$ 行 $k$ 列的正方形。一个集装箱的坐标为其中心格子的坐标。集装箱可以向上下左右移动，但不能碰到障碍物，且不能移出仓库的边界。

给定 $q$ 对格子 $A_k$ 和 $B_k$，对于每对格子，请找到能从 $A_k$ 移动到 $B_k$ 的集装箱的最大尺寸，注意这个尺寸也要是一个奇数。

输入格式

第一行包含一个正整数 $n$（$2\le n \le 1000$），表示仓库的尺寸。

接下来 $n$ 行，每行 $n$ 个字符，描述整个仓库，其中 . 表示空格子，# 表示障碍物。

接下来一行包含一个正整数 $q$（$1\le q\le 300000$），表示询问的个数。

接下来 $q$ 行，每行四个正整数 $A_x,A_y,B_x,B_y$（$1\le A_x,A_y,B_x,B_y\le n$），分别表示 $A$ 和 $B$ 的坐标。

输入数据保证 $A$ 和 $B$ 是不同的空格子。

输出格式

输出 $q$ 行，每行一个整数，对于每个询问输出最大尺寸，如果不存在解，那么输出 $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