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_ {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 $之间的每种颜色至少有一个城市使用该颜色。

对于每个任务，从$ (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) $ .