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$$$ 个整数。在第 $$$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$$$ 之间的每种颜色,至少有一个该颜色的城市。
输出
对于每个任务,打印从单元格 $$$(r_1, c_1)$$$ 处的城市出发到达单元格 $$$(r_2, c_2)$$$ 处的城市的最短可能时间。
示例
输入 #1
3 4 5 1 2 1 3 4 4 5 5 1 2 1 3 2 1 1 3 4 2 2 2 2
输出 #1
2 0
输入 #2
4 4 8 1 2 2 8 1 3 4 7 5 1 7 6 2 3 8 8 4 1 1 2 2 1 1 3 4 1 1 2 4 1 1 4 4
输出 #2
2 3 3 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)$$$。