Problem: We have a grid with H rows and W columns. The square at the i-th row and the j-th column will be called Square (i,j).  The integers from 1 through H×W are written throughout the grid, and the integer written in Square (i,j) is A_{i,j}.  You, a magical girl, can teleport a piece placed on Square (i,j) to Square (x,y) by consuming |x-i|+|y-j| magic points.  You now have to take Q practical tests of your ability as a magical girl.  The i-th test will be conducted as follows:    * Initially, a piece is placed on the square where the integer L_i is written.    * Let x be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer x+D is written, as long as x is not R_i. The test ends when x=R_i.    * Here, it is guaranteed that R_i-L_i is a multiple of D.  For each test, find the sum of magic points consumed during that test.

Submission attempts (in order):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

h,w,d = li()
a = [list(li()) for _ in range(h)]

num2point = [(-1,-1)]*(h*w+1)
for r, ai in enumerate(a):
    for c, aij in enumerate(ai):
        num2point[aij] = (r, c)
    

dist = [[] for _ in range(d)]
for num in range(h*w):
    i = num+1
    if i // d == 0:
        dist[i%d].append(0)
        
    else:
        dist[i%d].append(abs(num2point[i][0]-num2point[i-d][0]) + abs(num2point[i][1]-num2point[i-d][1]))
        
dist_cum = [list(accumulate(dist_row)) for dist_row in dist]


q = ni()
for _ in range(q):
    l,r = li()
    print(dist_cum[l%d][r//d] - dist_cum[l%d][l//d])

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

h,w,d = li()
a = [list(li()) for _ in range(h)]

num2point = [(-1,-1)]*(h*w+1)
for r, ai in enumerate(a):
    for c, aij in enumerate(ai):
        num2point[aij] = (r, c)
    

dist = [[] for _ in range(d)]
for num in range(h*w):
    i = num+1
    if i // d == 0 or i == d:
        dist[i%d].append(0)
        
    else:
        dist[i%d].append(abs(num2point[i][0]-num2point[i-d][0]) + abs(num2point[i][1]-num2point[i-d][1]))
        
dist_cum = [list(accumulate(dist_row)) for dist_row in dist]


q = ni()
for _ in range(q):
    l,r = li()
    print(dist_cum[l%d][r//d] - dist_cum[l%d][l//d])

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

h,w,d = li()
a = [list(li()) for _ in range(h)]

num2point = [(-1,-1)]*(h*w)
for r, ai in enumerate(a):
    for c, aij in enumerate(ai):
        num2point[aij-1] = (r, c)
    

dist = [[] for _ in range(d)]
for i in range(h*w):
    if i // d == 0:
        dist[i%d].append(0)
        
    else:
        dist[i%d].append(abs(num2point[i][0]-num2point[i-d][0]) + abs(num2point[i][1]-num2point[i-d][1]))
        
dist_cum = [list(accumulate(dist_row)) for dist_row in dist]


q = ni()
for _ in range(q):
    l,r = li_()
    print(dist_cum[l%d][r//d] - dist_cum[l%d][l//d])

Verdicts: Runtime Error

Runtime Error

Accepted