;; -*- coding:utf-8 -*-

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter O3 '(optimize (speed 3) (safety 0) (debug 0)))
  (defparameter O2 '(optimize (speed 3) (safety 1))))

(defmacro print-line (obj &optional (stream '*standard-output*))
  `(prog1 (princ ,obj ,stream) (terpri ,stream)))


;; Hauptteil

(defmacro split-and-bind (arg-lst string &body body)
  (let ((pos1 (gensym "POS"))
	(pos2 (gensym "POS"))
	(str-evaled (gensym "STR")))
    (labels ((expand (arg-lst &optional (init-pos1 t))
	       (if (null arg-lst)
		   body
		   `((let* ((,pos1 ,(if init-pos1 0 `(1+ ,pos2)))
			    (,pos2 (position #\space ,str-evaled :start ,pos1 :test #'char=))
			    (,(car arg-lst) (parse-integer ,str-evaled :start ,pos1 :end ,pos2)))
		       ,@(expand (cdr arg-lst) nil))))))
      `(let ((,str-evaled ,string))
	 ,@(expand arg-lst)))))

(declaim (inline l1-norm))
(defun l1-norm (x1 y1 x2 y2)
  (+ (abs (- x1 x2)) (abs (- y1 y2))))

(deftype unum nil `(integer 0 ,(expt 10 9)))
(defun main ()
  (declare #.O3)
  (let* ((height (read))
	 (width (read))
	 (delta (read))
	 (adict-row (make-array (* width height)
				:initial-element 0 :element-type 'unum))
	 (adict-col (make-array (* width height)
				:initial-element 0 :element-type 'unum)))
    (declare (unum width height delta))
    (labels ((dist (a1 a2)
	       (l1-norm (aref adict-row a1) (aref adict-col a1)
			(aref adict-row a2) (aref adict-col a2))))
      (declare (unum width height delta))
    (loop for row from 0 below height do
	 (loop for col from 0 below width do
	      (let ((a (- (read) 1)))
		(setf (aref adict-row a) row)
		(setf (aref adict-col a) col))))
    (let* ((q (read))
	   (l-arr (make-array q :initial-element 0 :element-type 'unum))
	   (r-arr (make-array q :initial-element 0 :element-type 'unum)))
      (dotimes (idx q)
	(split-and-bind (l r) (the string (read-line))
	  (declare (unum l r))
	  (setf (aref l-arr idx) (- l 1)
		(aref r-arr idx) (- r 1))))
      (let ((cumul-mp (make-array (* width height)
				  :initial-element 0
				  :element-type 'unum)))
	(loop for rem from 0 below delta
	   do (loop for a from rem below (* width height) by delta
		 for mp = 0 then (+ mp (dist (- a delta) a))
		 do (setf (aref cumul-mp a) mp)))
	(loop for idx from 0 below q
	   do (let ((left (aref l-arr idx))
		    (right (aref r-arr idx)))
		(print-line (- (aref cumul-mp right)
			       (aref cumul-mp left))))))))))
      


#-swank(main)


;; Für Test
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "C:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

(defun test ()
  (with-input-from-string (*standard-input* (delete #\return (get-clipbrd)))
    (main)))


;; Für Benchmark
(defparameter *file-path* *load-pathname*)
(defparameter *dir-path* (pathname (directory-namestring *file-path*)))
(defparameter *dat-path* (merge-pathnames "test.dat" *dir-path*))

#+swank
(defun gendat ()
  (with-open-file (out *dat-path*
		       :direction :output :if-exists :supersede)
    ))

(defun bench ()
  (let ((*standard-output* (make-broadcast-stream)))
    (with-open-file (*standard-input* *dat-path*)
      (time (main)))))


Measured memory_bytes: 72808