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