Buggy python submission (verdict: Time Limit Exceeded):
nTmp  = input().rstrip().split(' ')
nH = int(nTmp[0])
nW = int(nTmp[1])
nD = int(nTmp[2])

nS = nH * nW
Ans = 0

nDataH = [0 for i in range(nS + 1)]
nDataW = [0 for i in range(nS + 1)]

for i in range(nH):
    sTmp = input().rstrip().split(' ')
    
    for i2 in range(nW):
        nNum = int (sTmp[i2])
        nDataH[nNum] = i
        nDataW[nNum] = i2

nQ = int(input())

Data = {}

for i in range(nQ):
    nDis = 0
    sTmp = input().rstrip().split(' ')
    nL = int(sTmp[0])
    nR = int(sTmp[1])
    nCnt = (nR - nL) // nD


    if nCnt == 0:
        print('0')
    else:
        nPoi=('%d-%d' %(nL,nR))

        if Data.get(nPoi):
            print(Data[nPoi])
            continue


        for i2 in range(nCnt):
            

            nL2 = nL + nD
            nTmpDis = nDataH[nL2] - nDataH[nL] 
            if nTmpDis < 0:
                nTmpDis *= -1
            nDis += nTmpDis
            nTmpDis = nDataW[nL2] - nDataW[nL] 
            if nTmpDis < 0:
                nTmpDis *= -1
            nDis += nTmpDis
            nL = nL2
        
        Data[nPoi] = nDis
        
        print(nDis)        


Fixed submission:
nTmp  = input().rstrip().split(' ')
nH = int(nTmp[0])
nW = int(nTmp[1])
nD = int(nTmp[2])

nS = nH * nW
Ans = 0

nDataH = [0 for i in range(nS + 1)]
nDataW = [0 for i in range(nS + 1)]

for i in range(nH):
    sTmp = input().rstrip().split(' ')
    
    for i2 in range(nW):
        nNum = int (sTmp[i2])
        nDataH[nNum] = i
        nDataW[nNum] = i2

nQ = int(input())

nDis = [0 for i in range(nS + 1)]

for i in range(nS + 1):
    nDis[i] = 0
    if i <= nD:
        continue
    
    nTmpDis = nDataH[i] - nDataH[i - nD] 
    if nTmpDis < 0:
        nTmpDis *= -1
    nDis[i] += nTmpDis
    nTmpDis = nDataW[i] - nDataW[i - nD] 
    if nTmpDis < 0:
        nTmpDis *= -1
    nDis[i] += nTmpDis
    nDis[i] += nDis[i - nD]

for i in range(nQ):
    sTmp = input().rstrip().split(' ')
    nL = int(sTmp[0])
    nR = int(sTmp[1])
    Ans = nDis[nR] - nDis[nL]
    print(Ans)

Buggy python submission (verdict: Time Limit Exceeded):
nTmp  = input().rstrip().split(' ')
nH = int(nTmp[0])
nW = int(nTmp[1])
nD = int(nTmp[2])

nS = nH * nW
Ans = 0

nDataH = [0 for i in range(nS + 1)]
nDataW = [0 for i in range(nS + 1)]

for i in range(nH):
    sTmp = input().rstrip().split(' ')
    
    for i2 in range(nW):
        nNum = int (sTmp[i2])
        nDataH[nNum] = i
        nDataW[nNum] = i2

nQ = int(input())

for i in range(nQ):
    nDis = 0
    sTmp = input().rstrip().split(' ')
    nL = int(sTmp[0])
    nR = int(sTmp[1])
    nCnt = (nR - nL) // nD

    if nCnt == 0:
        print('0')
    else:
        for i2 in range(nCnt):
            nL2 = nL + nD
            nTmpDis = nDataH[nL2] - nDataH[nL] 
            if nTmpDis < 0:
                nTmpDis *= -1
            nDis += nTmpDis
            nTmpDis = nDataW[nL2] - nDataW[nL] 
            if nTmpDis < 0:
                nTmpDis *= -1
            nDis += nTmpDis
            nL = nL2
            
        
        print(nDis)        



Fixed submission:
nTmp  = input().rstrip().split(' ')
nH = int(nTmp[0])
nW = int(nTmp[1])
nD = int(nTmp[2])

nS = nH * nW
Ans = 0

nDataH = [0 for i in range(nS + 1)]
nDataW = [0 for i in range(nS + 1)]

for i in range(nH):
    sTmp = input().rstrip().split(' ')
    
    for i2 in range(nW):
        nNum = int (sTmp[i2])
        nDataH[nNum] = i
        nDataW[nNum] = i2

nQ = int(input())

nDis = [0 for i in range(nS + 1)]

for i in range(nS + 1):
    nDis[i] = 0
    if i <= nD:
        continue
    
    nTmpDis = nDataH[i] - nDataH[i - nD] 
    if nTmpDis < 0:
        nTmpDis *= -1
    nDis[i] += nTmpDis
    nTmpDis = nDataW[i] - nDataW[i - nD] 
    if nTmpDis < 0:
        nTmpDis *= -1
    nDis[i] += nTmpDis
    nDis[i] += nDis[i - nD]

for i in range(nQ):
    sTmp = input().rstrip().split(' ')
    nL = int(sTmp[0])
    nR = int(sTmp[1])
    Ans = nDis[nR] - nDis[nL]
    print(Ans)