题目背景

在 2018 年的 ICPC 南京站中，K 题《袋鼠谜题》要求选手构造一个操作序列，使得所有袋鼠聚集到同一格子中。此后，2020 年（A 题《啊，昨日重现》）、2021 年（A 题《呀，昨日再次重现》）、2022 年（A 题《停停，昨日请不要再重现》）、2023 年（A 题《酷，昨日四次重现》）、2024 年（A 题 《嘿，有看到我的袋鼠吗？》）的竞赛中，每年都有一道与袋鼠相关的题目。

作为袋鼠爱好者，$\text{Setsuna}$ 在南师 2023 年的迎新生赛中提出了 M 题《哈，昨日五次重现》，要求以最少代价使得目标袋鼠成为最后赢家。那么今年也不例外，题面可描述如下。

题目描述

出题人们连年迫害袋鼠，而现在已经是 3024 年，总是掉到坑中的袋鼠早就灭绝了！

现在的袋鼠学会了九十九种法术，因此可以跳得很远！具体来说，若袋鼠当前在 $(a,b)$ 点，则一步可以跳到 $(c,d)$ 点，但这要求袋鼠的跳跃能力至少为 $(a-c)^2+(b-d)^2$，否则无法进行跳跃。

给定一个 $n\times m$ 的网格，其中某些位置有坑，其他位置则是平地。袋鼠们每次跳跃后，其终点必须是平地。有 $q$ 次询问，每次询问请回答：

• 位于 $(s_x,s_y)$ 的袋鼠，至少需要多大的跳跃能力，才能经过（可能多次）跳跃到达 $(t_x,t_y)$？

输入格式

第一行两个整数 $n, m$，表示网格大小。

接下来 $n$ 行每行一个长度为 $m$ 的字符串，仅由字符 'o' 和 'x' 构成。其中 'x' 表示此处有坑，而 'o' 表示此处为平地。

接下来一行一个整数 $q$，表示询问次数。

接下来 $q$ 行每行四个整数 $s_x,s_y,t_x,t_y$，表示袋鼠初始位置在第 $s_x$ 行第 $s_y$ 列，希望跳到第 $t_x$ 行第 $t_y$ 列。

输出格式

对于每次询问输出一行一个正整数，表示最少需要的跳跃能力。

样例输入1

4 5
ooxxo
oxxox
xxoox
xoxxo
3
1 2 2 1
1 1 3 3
4 2 4 5

样例输出1

1
5
2

样例 1 解释

第一次询问：$(1,2)\to (1,1)\to (2,1)$，只需要 $1$ 的跳跃能力。

第二次询问：$(1,1)\to (2,1)\to (3,3)$，需要 $(2-3)^2+(1-3)^2=5$ 的跳跃能力。

第三次询问：$(4,2)\to (3,3)\to (3,4)\to (4,5)$，需要 $2$ 的跳跃能力。

数据范围与约定

对于 50% 的数据, $1\le n,m\le 10, 1\le q \le 50$。

对于 100% 的数据, $1\le n,m\le 2\times 10^3, n\times m\le 5\times 10^3, 1\le q\le 2\times 10^5$。

$1\le s_x,t_x\le n, 1\le s_y,t_y\le m$

保证 $(s_x,s_y)$ 处和 $(t_x,t_y)$ 处是平地，$(s_x,s_y)\neq (t_x,t_y)$。