CF1301F.Super Jaber

Jaber is a superhero in a large country that can be described as a grid with $n$ rows and $m$ columns, where every cell in that grid contains a different city.

Jaber gave every city in that country a specific color between $1$ and $k$. In one second he can go from the current city to any of the cities adjacent by the side or to any city with the same color as the current city color.

Jaber has to do $q$ missions. In every mission he will be in the city at row $r_1$ and column $c_1$, and he should help someone in the city at row $r_2$ and column $c_2$.

Jaber wants your help to tell him the minimum possible time to go from the starting city to the finishing city for every mission.

贾贝尔是一个超级英雄，他所在的国家可以被描述为一个 $n$ 行 $m$ 列的网格，该网格中每个单元格都对应一座不同的城市。

贾贝尔为该国每座城市分配了一个介于 $1$ 到 $k$ 之间的特定颜色。每秒，他可以从当前城市移动到任意一个与其上下左右相邻的城市，或者移动到任意一座与当前城市颜色相同的城市。

贾贝尔需要执行 $q$ 项任务。在每一项任务中，他起始于第 $r_1$ 行、第 $c_1$ 列的城市，并需抵达第 $r_2$ 行、第 $c_2$ 列的城市以提供帮助。

贾贝尔希望你帮他计算：对每一项任务，从起点城市到达终点城市的最短可能耗时。

The first line contains three integers $n$, $m$ and $k$ ($1 \leq n, m \leq 1000$, $1 \leq k \leq min(40 , n \cdot m)$) — the number of rows, columns and colors.

Each of the next $n$ lines contains $m$ integers. In the $i$-th line, the $j$-th integer is $a_{ij}$ ($1 \leq a_{ij} \leq k$), which is the color assigned to the city in the $i$-th row and $j$-th column.

The next line contains one integer $q$ ($1 \leq q \leq 10^{5}$) — the number of missions.

For the next $q$ lines, every line contains four integers $r_1$, $c_1$, $r_2$, $c_2$ ($1 \leq r_1 , r_2 \leq n$, $1 \leq c_1 , c_2 \leq m$) — the coordinates of the starting and the finishing cities of the corresponding mission.

It is guaranteed that for every color between $1$ and $k$ there is at least one city of that color.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 1000$，$1 \leq k \leq \min(40 , n \cdot m)$），分别表示行数、列数和颜色种类数。

接下来的 $n$ 行，每行包含 $m$ 个整数。在第 $i$ 行中，第 $j$ 个整数为 $a_{ij}$（$1 \leq a_{ij} \leq k$），表示位于第 $i$ 行、第 $j$ 列的城市所分配的颜色。

接下来一行包含一个整数 $q$（$1 \leq q \leq 10^{5}$），表示任务的数量。

随后的 $q$ 行中，每行包含四个整数 $r_1$、$c_1$、$r_2$、$c_2$（$1 \leq r_1 , r_2 \leq n$，$1 \leq c_1 , c_2 \leq m$），分别表示对应任务的起始城市与目标城市的坐标。

保证对于从 $1$ 到 $k$ 的每一种颜色，至少存在一个该颜色的城市。

For every mission print the minimum possible time to reach city at the cell $(r_2, c_2)$ starting from city at the cell $(r_1, c_1)$.

对于每个任务，输出从单元格 $(r_1, c_1)$ 处的城市出发，到达单元格 $(r_2, c_2)$ 处的城市所需的最短时间。

In the first example:

• mission $1$: Jaber should go from the cell $(1,1)$ to the cell $(3,3)$ because they have the same colors, then from the cell $(3,3)$ to the cell $(3,4)$ because they are adjacent by side (two moves in total);
• mission $2$: Jaber already starts in the finishing cell.

In the second example:

• mission $1$: $(1,1)$ $\rightarrow$ $(1,2)$ $\rightarrow$ $(2,2)$;
• mission $2$: $(1,1)$ $\rightarrow$ $(3,2)$ $\rightarrow$ $(3,3)$ $\rightarrow$ $(3,4)$;
• mission $3$: $(1,1)$ $\rightarrow$ $(3,2)$ $\rightarrow$ $(3,3)$ $\rightarrow$ $(2,4)$;
• mission $4$: $(1,1)$ $\rightarrow$ $(1,2)$ $\rightarrow$ $(1,3)$ $\rightarrow$ $(1,4)$ $\rightarrow$ $(4,4)$.

在第一个例子中：

• 任务 $1$：Jaber 应从单元格 $(1,1)$ 出发，前往单元格 $(3,3)$（因为二者颜色相同），再从单元格 $(3,3)$ 前往单元格 $(3,4)$（因为二者边相邻），共需两步；
• 任务 $2$：Jaber 起始位置即为终点单元格。

在第二个例子中：

• 任务 $1$：$(1,1)$ $\rightarrow$ $(1,2)$ $\rightarrow$ $(2,2)$；
• 任务 $2$：$(1,1)$ $\rightarrow$ $(3,2)$ $\rightarrow$ $(3,3)$ $\rightarrow$ $(3,4)$；
• 任务 $3$：$(1,1)$ $\rightarrow$ $(3,2)$ $\rightarrow$ $(3,3)$ $\rightarrow$ $(2,4)$；
• 任务 $4$：$(1,1)$ $\rightarrow$ $(1,2)$ $\rightarrow$ $(1,3)$ $\rightarrow$ $(1,4)$ $\rightarrow$ $(4,4)$。