CF2045G X Aura

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”。否则，输出一个整数，表示从起始单元格到目标单元格的最小总惩罚。

Explanation for the sample input/output #1 For the first scenario, one of the solutions is to move as follows: $ (1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4) $ . The total penalty of this solution is $ (3 - 4)^1 + (4 - 3)^1 + (3 - 6)^1 + (6 - 8)^1 + (8 - 1)^1 = 2 $ . Explanation for the sample input/output #2 For the first scenario, the cycle $ (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (1, 1) $ has a penalty of $ (1 - 2)^5 + (2 - 0)^5 + (0 - 9)^5 + (9 - 1)^5 = -26250 $ . You can keep repeating this cycle to make your total penalty arbitrarily small. Similarly, for the second scenario, you can move to $ (1, 1) $ first, then repeat the same cycle.