说明

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

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

2
4
-7
-1
0

2 4 5
1908
2023
2
1 1 2 4
1 1 1 1

INVALID
INVALID

提示

样例输入/输出 #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)$，然后重复相同的循环。

翻译由 DeepSeek V3.2 完成