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)$，并使总惩罚值最小。在某些场景中，总惩罚值可能会变得任意小；这种场景被称为 INVALID（无效）。请找出从起始单元格移动到终点单元格的最小总惩罚值，或者判断该场景是否无效。

输入格式

第一行包含三个整数 $R$、$C$、$X$ ($1 \le R, C \le 1000$; $1 \le X \le 9$; $X$ 为奇数)。

接下来的 $R$ 行，每行包含一个长度为 $C$ 的字符串 $H_r$。$H_r$ 中的每个字符都是 0 到 9 之间的数字。$H_r$ 的第 $c$ 个字符表示单元格 $(r, c)$ 的高度 $H_{r,c}$。

下一行包含一个整数 $Q$ ($1 \le Q \le 100\,000$)。

接下来的 $Q$ 行，每行包含四个整数 $R_s$、$C_s$、$R_f$、$C_f$ ($1 \le R_s, R_f \le R$; $1 \le C_s, C_f \le 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

说明 1

对于第一个场景，其中一种移动方案是：$(1, 1) \to (2, 1) \to (3, 1) \to (3, 2) \to (3, 3) \to (3, 4)$。该方案的总惩罚值为 $(3 - 4)^1 + (4 - 3)^1 + (3 - 6)^1 + (6 - 8)^1 + (8 - 1)^1 = 2$。

输入 2

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

输出 2

INVALID
INVALID

说明 2

对于第一个场景，循环 $(1, 1) \to (2, 1) \to (2, 2) \to (1, 2) \to (1, 1)$ 的惩罚值为 $(1 - 2)^5 + (2 - 0)^5 + (0 - 9)^5 + (9 - 1)^5 = -26250$。你可以不断重复这个循环，使总惩罚值变得任意小。同样地，对于第二个场景，你可以先移动到 $(1, 1)$，然后重复相同的循环。

输入 3

3 3 9
135
357
579
2
3 3 1 1
2 2 2 2

输出 3

2048
0