CF1301F Super Jaber

Jaber 是一个大国家的超级英雄，该国可以描述为一个具有 $ n $ 行和 $ m $ 列的网格，其中网格中的每个单元格都包含一个不同的城市。 Jaber 给该国的每个城市都指定了 $ 1 $ 到 $ k $ 的特定颜色。一秒钟之内，他可以从当前城市转到相邻（左右相邻或上下相邻，即四连通）的任何城市，或者到与当前城市颜色相同颜色的任何城市。 Jaber 必须执行 $ q $ 个任务。在每个任务中，他都会在 $ r_1 $ 行和 $ c_1 $ 列所在的城市中，他应该在 $ r_2 $ 行和 $ c_2 $ 列中帮助该城市中的某个人。 Jaber 需要你的帮助，告诉他每次任务从出发城市到终点城市的最短时间。

第一行包含三个整数 $ n , m $ 和 $ k $（$ 1 \leq n, m \leq 1000 , 1 \leq k \leq \min(40 , n \cdot m) $）——分别代表行数，列数和颜色值。 接下来的 $ n $ 行中的每行包含 $ m $ 个整数 $ a_ {i,j} $（$ 1 \leq a_{i,j} \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 $ 之间的每种颜色至少有一个城市使用该颜色。

对于每个任务，从 $ (r_1, c_1) $ 单元格中的城市开始，打印到达 $ (r_2, c_2) $ 单元格中的城市所需的最短时间。

在第一个样例中： - 任务 $ 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) $ .