package main

import (
	"bufio"
	"fmt"
	"os"
)

type FastScanner struct {
	r *bufio.Reader
}

func NewFastScanner() *FastScanner {
	return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}

func (fs *FastScanner) nextByte() (byte, error) {
	return fs.r.ReadByte()
}

func (fs *FastScanner) unreadByte() {
	_ = fs.r.UnreadByte()
}

func (fs *FastScanner) skipSpaces() error {
	for {
		b, err := fs.nextByte()
		if err != nil {
			return err
		}
		if b > ' ' {
			fs.unreadByte()
			return nil
		}
	}
}

func (fs *FastScanner) NextInt() (int, error) {
	if err := fs.skipSpaces(); err != nil {
		return 0, err
	}
	sign := 1
	val := 0
	b, err := fs.nextByte()
	if err != nil {
		return 0, err
	}
	if b == '-' {
		sign = -1
	} else if b >= '0' && b <= '9' {
		val = int(b - '0')
	} else {
		return 0, fmt.Errorf("invalid int")
	}
	for {
		b, err = fs.nextByte()
		if err != nil {
			break
		}
		if b < '0' || b > '9' {
			fs.unreadByte()
			break
		}
		val = val*10 + int(b-'0')
	}
	return sign * val, nil
}

func (fs *FastScanner) NextToken() (string, error) {
	if err := fs.skipSpaces(); err != nil {
		return "", err
	}
	buf := make([]byte, 0, 64)
	for {
		b, err := fs.nextByte()
		if err != nil {
			if len(buf) == 0 {
				return "", err
			}
			return string(buf), nil
		}
		if b <= ' ' {
			break
		}
		buf = append(buf, b)
	}
	return string(buf), nil
}

func main() {
	in := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	R, err := in.NextInt()
	if err != nil {
		return
	}
	C, _ := in.NextInt()
	X, _ := in.NextInt()

	N := R * C
	h := make([]byte, N)

	for r := 0; r < R; r++ {
		s, _ := in.NextToken()
		for c := 0; c < C; c++ {
			h[r*C+c] = s[c] - '0'
		}
	}

	// Precompute d^X for d in [-9..9]
	powVal := make([]int64, 19)
	for d := -9; d <= 9; d++ {
		val := int64(1)
		for i := 0; i < X; i++ {
			val *= int64(d)
		}
		powVal[d+9] = val
	}

	invalid := false
	if R >= 2 && C >= 2 {
		for r := 0; r < R-1 && !invalid; r++ {
			row := r * C
			row2 := (r + 1) * C
			for c := 0; c < C-1; c++ {
				A := int(h[row+c])
				B := int(h[row+c+1])
				Cc := int(h[row2+c])
				D := int(h[row2+c+1])
				S := powVal[A-B+9] + powVal[B-D+9] + powVal[D-Cc+9] + powVal[Cc-A+9]
				if S != 0 {
					invalid = true
					break
				}
			}
		}
	}

	Q, _ := in.NextInt()
	if invalid {
		for i := 0; i < Q; i++ {
			// consume query
			_, _ = in.NextInt()
			_, _ = in.NextInt()
			_, _ = in.NextInt()
			_, _ = in.NextInt()
			fmt.Fprintln(out, "INVALID")
		}
		return
	}

	// Build potential phi via BFS
	phi := make([]int64, N)
	vis := make([]bool, N)
	q := make([]int, 0, N)
	push := func(v int) {
		q = append(q, v)
	}
	pop := func() int {
		v := q[0]
		q = q[1:]
		return v
	}
	vis[0] = true
	phi[0] = 0
	push(0)

	for len(q) > 0 {
		u := pop()
		ur := u / C
		uc := u % C
		hu := int(h[u])
		// up
		if ur > 0 {
			v := u - C
			if !vis[v] {
				hv := int(h[v])
				phi[v] = phi[u] + powVal[hu-hv+9]
				vis[v] = true
				push(v)
			}
		}
		// down
		if ur+1 < R {
			v := u + C
			if !vis[v] {
				hv := int(h[v])
				phi[v] = phi[u] + powVal[hu-hv+9]
				vis[v] = true
				push(v)
			}
		}
		// left
		if uc > 0 {
			v := u - 1
			if !vis[v] {
				hv := int(h[v])
				phi[v] = phi[u] + powVal[hu-hv+9]
				vis[v] = true
				push(v)
			}
		}
		// right
		if uc+1 < C {
			v := u + 1
			if !vis[v] {
				hv := int(h[v])
				phi[v] = phi[u] + powVal[hu-hv+9]
				vis[v] = true
				push(v)
			}
		}
	}

	for i := 0; i < Q; i++ {
		Rs, _ := in.NextInt()
		Cs, _ := in.NextInt()
		Rf, _ := in.NextInt()
		Cf, _ := in.NextInt()
		s := (Rs - 1) * C + (Cs - 1)
		t := (Rf - 1) * C + (Cf - 1)
		ans := phi[t] - phi[s]
		fmt.Fprintln(out, ans)
	}
}