X Aura

Mount ICPC can be represented as a grid of $R$ rows (numbered from $1$ to $R$) and $C$ columns (numbered from $1$ to $C$). The cell at row $r$ and column $c$ is denoted $(r, c)$ and has height $H_{r,c}$. Two cells are adjacent if they share a side. So $(r, c)$ is adjacent to $(r - 1, c)$, $(r + 1, c)$, $(r, c - 1)$, and $(r, c + 1)$, whenever those cells exist.

You can move only between adjacent cells, and each move has a penalty. With an aura $X$, which is an odd positive integer, moving from a cell with height $h_1$ to a cell with height $h_2$ gives a penalty of $(h_1-h_2)^X$. The penalty can be negative.

There are $Q$ independent scenarios. In each one, you start at cell $(R_s, C_s)$ and want to reach cell $(R_f, C_f)$ with the minimum total penalty. In some scenarios the total penalty can become arbitrarily small. Such a scenario is called invalid. For each scenario, find the minimum total penalty, or determine that it is invalid.

The first line contains three integers $R$, $C$, and $X$ ($1 \le R, C \le 1000$; $1 \le X \le 9$; $X$ is odd).

Each of the next $R$ lines contains a string $H_r$ of length $C$. Each character is a digit from 0 to 9. The $c$-th character of $H_r$ is the height $H_{r,c}$ of cell $(r, c)$.

The next line contains an integer $Q$ ($1 \le Q \le 100\,000$).

Each of the next $Q$ lines contains four integers $R_s$ $C_s$ $R_f$ $C_f$ ($1 \le R_s, R_f \le R$; $1 \le C_s, C_f \le C$).

For each scenario, print one line. If the scenario is invalid, print INVALID. Otherwise, print the minimum total penalty from the starting cell to the destination cell as an integer.