403010 - 超级英雄

一个国家可以看作 n 行 m 列的网格，每个格子代表一座城市，每座城市被染为 1 ~ k 中的一种颜色。 超级英雄每秒可以进行两种移动方式任选其一：

1. 移动到四连通相邻的城市；
2. 瞬间传送到任意一个和当前城市颜色相同的城市。 共有 q 次询问，每次给出起点坐标 (r1, c1)、终点坐标 (r2, c2)，求从起点到达终点的最短时间。

第一行包含三个整数 n，m 和 k ( 1 ≤ n, m ≤ 1000 , 1 ≤ k ≤ min(40, n⋅m) )，分别代表行数，列数和颜色值。 接下来的 n 行中的每行包含 m 个整数 aij ( 1 ≤ aij ≤ k ) 代表第 i 行， 第 j 列的城市被分配的颜色值。 下一行包含一个整数 q ( 1 ≤ q ≤ 10^5 )，代表任务数。 对于接下来的 q 行，每行包含四个整数 r1，c1，r2，c2 ( 1 ≤ r1, r2 ≤ n, 1 ≤ c1, c2 ≤ m）相应任务的起点和终点城市的坐标。 保证在 1 和 k 之间的每种颜色至少有一个城市使用该颜色。

对于每个任务，从 (r1, c1) 单元格中的城市开始，打印到达 (r2, c2) 单元格中的城市所需的最短时间。

在第一个样例中： 任务1：超级英雄应该从单元格（1, 1）到单元格（3, 3），因为它们具有相同的颜色，然后从单元格（3, 3）到单元格（3, 4），因为它们并排相邻（总共移动了两个）； 任务2：超级英雄已经在终点位置。 在第二个样例中： 任务 1 : (1, 1) → (1, 2) → (2, 2) ; 任务 2 : (1, 1) → (3, 2) → (3, 3) → (3, 4) ; 任务 3 : (1, 1) → (3, 2) → (3, 3) → (2, 4) ; 任务 4 : (1, 1) → (1, 2) → (1, 3) → (1, 4) → (4, 4)。