给定一个 $n \times n$ 的网格，每个单元格要么是陆地，要么是水域。网格的行和列编号为 $1, 2, \dots, n$。你可以在网格中通过向左、向右、向上或向下移动来行走。如果两个单元格可以通过一步或多步移动到达，且移动过程中始终保持在同类型的单元格内，则称这两个单元格是连通的。
陆地单元格构成一个连通的岛屿，水域单元格构成一个连通的海洋。第一行、最后一行、第一列和最后一列仅包含水域单元格。
你的任务是回答 $q$ 个询问：给定两个陆地单元格 $(r_1, c_1)$ 和 $(r_2, c_2)$，求在始终保持在陆地上的前提下，从第一个单元格移动到第二个单元格所需的最少步数。
输入格式
第一行包含两个整数 $n$ 和 $q$：网格的大小和询问的数量。
接下来的 $n$ 行，每行包含 $n$ 个字符，描述网格。其中 "." 表示水域单元格，"#" 表示陆地单元格。
接下来的 $q$ 行，每行包含四个整数 $r_1, c_1, r_2, c_2$：第一个单元格的行和列，以及第二个单元格的行和列。
输出格式
按顺序输出每个询问的答案，每行一个。
数据范围
- $3 \le n \le 1000$
- $1 \le q \le 10^5$
- $1 < r_1, c_1, r_2, c_2 < n$ 对于所有询问均成立
样例
输入 1
8 4 ........ ..####.. .##.###. .##.###. .#...... .#####.. ..#####. ........ 2 3 3 7 4 5 4 5 4 7 7 7 6 2 3 2
输出 1
5 0 17 3
子任务
| 子任务 | 约束条件 | 分值 |
|---|---|---|
| 1 | $n \le 200, q \le 200$ | 10 |
| 2 | 陆地单元格之间不存在水域单元格的行或列 | 6 |
| 3 | 不存在 $2 \times 2$ 的全陆地正方形 | 16 |
| 4 | 陆地单元格之间不存在水域单元格的行 | 28 |
| 5 | 无额外约束 | 40 |