#include <bits/stdc++.h>
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
const int INF = 2e9;
int H, W, L, Q;
int a[3005][3005];
int pos[3005][3005];
bool check[3005][3005];
bool reach[3005][3005];
int encode(int x, int y) {
return (x - 1) * W + y;
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("02-28.txt", "r", stdin);
std::cin.tie(0)->sync_with_stdio(0);
std::cin >> H >> W >> L;
for (int i = 1; i <= H; ++i) {
for (int j = 1; j <= W; ++j) {
std::cin >> a[i][j];
}
}
for (int i = 1; i <= H; ++i) {
for (int j = 1; j <= W; ++j) {
int id = encode(i, j);
std::vector<std::pair<int, int>> vec;
std::queue<std::pair<int, int>> q;
q.push({i, j});
while (!q.empty()) {
auto [x, y] = q.front();
vec.push_back({x, y});
reach[id][encode(x, y)] = true;
q.pop();
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k];
int ny = y + dy[k];
if (1 <= nx && nx <= H && 1 <= ny && ny <= W && !check[nx][ny] && a[nx][ny] <= a[i][j] + L) {
check[nx][ny] = true;
q.push({nx, ny});
}
}
}
pos[0][id] = (pos[1][id] = id);
int mx = a[i][j];
for (auto [x, y] : vec) {
if (a[x][y] > mx) {
pos[1][id] = encode(x, y);
mx = a[x][y];
}
check[x][y] = false;
}
}
}
for (int i = 1; i <= H * W; ++i) {
for (int j = 1; j <= H * W; ++j) {
pos[j][i] = pos[1][pos[j - 1][i]];
}
}
std::cin >> Q;
for (int i = 1; i <= Q; ++i) {
int a, b, x, y; std::cin >> a >> b >> x >> y;
a = encode(a, b);
x = encode(x, y);
int l = 0, r = H * W, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (reach[pos[mid][a]][x]) {
ans = mid + 1;
r = mid - 1;
} else {
l = mid + 1;
}
}
std::cout << ans << '\n';
}
return 0;
}
