X 아우라

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$이 주어진다. 각 문자는 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를 출력한다. 그렇지 않으면 시작 칸에서 도착 칸까지의 총 페널티 최솟값을 정수로 출력한다.