import Control.Monad
import Data.Array
import qualified Data.ByteString.Char8 as BS
main=do
 [h,w,d]<-map (read.BS.unpack).BS.words<$>BS.getLine
 a<-replicateM h (map (read.BS.unpack).BS.words<$>BS.getLine)
 q<-readLn
 lr<-replicateM q (map (read.BS.unpack).BS.words<$>BS.getLine)

 mapM_ print (reverse(k lr d [] (f (h*w) d (array (1,h*w) (zip (foldr (++) [] a) [(x,y)|x<-[1..h],y<-[1..w]])) 1 [] [(1,0)])))
  where f m d a i l ((x,y):n) |i==d+1    = array (1,d) (zip [d,(d-1)..1] l)
                              |x+d>m     = f m d a (i+1) ((array (1,m) ((x,y):n)):l) [(i+1,0)]
                              |otherwise = f m d a i l ((x+d,y+(g(a!x)(a!(x+d)))):((x,y):n))
        g (a,b) (c,d) = (abs (a-c))+(abs (b-d))
        k [] _ ans _ = ans
        k ([l,r]:lr) d ans pre = k lr d ((i l r (pre!((mod (l-1) d)+1))):ans) pre
        i l r a = (a!r)-(a!l)