G. X 光环
每个测试点时间限制：$1$ 秒
每个测试点内存限制：$1024$ 兆字节

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 \le R, C \le 1000$；$1 \le X \le 9$；$X$ 为奇数）。
接下来 $R$ 行，每行一个长度为 $C$ 的字符串 $H_r$。字符串中的每个字符是数字 $0$ 到 $9$，表示格子 $(r,c)$ 的高度 $H_{r,c}$。
下一行包含一个整数 $Q$（$1 \le Q \le 100000$）。
接下来 $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；否则，输出一个整数，表示从起点到终点的最小总代价。

样例

输入

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

输入

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

输出

2048
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：
第一个场景，存在一个循环 $(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)$，再重复该循环。