Mount ICPC 可以表示为 $$$R$$$ 行(编号从 $$$1$$$ 到 $$$R$$$)和 $$$C$$$ 列(编号从 $$$1$$$ 到 $$$C$$$)的网格。位于 $$$r$$$ 行和 $$$c$$$ 列的单元格表示为 $$$(r, c)$$$,高度为 $$$H_{r, c}$$$。如果两个单元共用一条边,则它们彼此相邻。形式上,$$$(r, c)$$$ 与 $$$(r-1, c)$$$、$$$(r+1, c)$$$、$$$(r, c-1)$$$ 和 $$$(r, c+1)$$$(如果存在)相邻。
你只能在相邻的单元格之间移动,并且每次移动都会受到惩罚。如果光环为奇数正整数 $$$X$$$,从高度为 $$$h_1$$$ 的单元格移动到高度为 $$$h_2$$$ 的单元格会给你带来 $$$(h_1 - h_2)^X$$$ 的惩罚。请注意,惩罚可以是负数。
您想要回答 $$$Q$$$ 独立场景。在每个场景中,您从起始单元格 $$$(R_s, C_s)$$$ 开始,并且希望以最小的总惩罚转到目标单元格 $$$(R_f, C_f)$$$。在某些情况下,总惩罚可能会变得任意小;这种情况称为无效。求从起始单元格移动到目标单元格的最小总惩罚,或确定场景是否无效。
输入
第一行由三个整数 $$$R$$$ $$$C$$$ $$$X$$$ ($$$1 \leq R, C \leq 1000; 1 \leq X \leq 9; X$$$ 是奇数)组成。
接下来的 $$$R$$$ 行均由长度为 $$$C$$$ 的字符串 $$$H_r$$$ 组成。 $$$H_r$$$ 中的每个字符都是从 0 到 9 的数字。$$$H_r$$$ 中的第 $$$c$$$ 字符表示单元格 $$$(r, c)$$$ 的高度,或 $$$H_{r, c}$$$。
下一行由整数 $$$Q$$$ ($$$1 \leq Q \leq 100\,000)$$$ 组成。
接下来的 $$$Q$$$ 行由四个整数 $$$R_s$$$ $$$C_s$$$ $$$R_f$$$ $$$C_f$$$ ($$$1 \leq R_s, R_f \leq R; 1 \leq C_s, C_f \leq C$$$) 组成。
输出
对于每个场景,在一行中输出以下内容。如果场景无效,则输出INVALID。否则,输出一个整数,表示从起始单元格移动到目标单元格的最小总惩罚。
示例
输入 #1
3 4 1 3359 4294 3681 5 1 1 3 4 3 3 2 1 2 2 1 4 1 3 3 2 1 1 1 1
输出 #1
2 4 -7 -1 0
输入 #2
2 4 5 1908 2023 2 1 1 2 4 1 1 1 1
输出 #2
INVALID INVALID
输入 #3
3 3 9 135 357 579 2 3 3 1 1 2 2 2 2
输出 #3
2048 0
注意
示例输入/输出 #1 的说明
对于第一种情况,解决方案之一是移动如下: $$$(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$$$。该解决方案的总惩罚为 $$$(3 - 4)^1 + (4 - 3)^1 + (3 - 6)^1 + (6 - 8)^1 + (8 - 1)^1 = 2$$$。
示例输入/输出#2 的说明
对于第一种情况,循环 $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (1, 1)$$$ 的惩罚为 $$$(1 - 2)^5 + (2 - 0)^5 + (0 - 9)^5 + (9 - 1)^5 = -26250$$$。你可以不断重复这个循环,使你的总惩罚变得任意小。同样,对于第二种情况,您可以先移动到 $$$(1, 1)$$$,然后重复相同的循环。