Problem:


Score : 400 points

Problem Statement

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.

Constraints

1 \leq H,W \leq 300

1 \leq D \leq H×W

1 \leq A_{i,j} \leq H×W

A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))

1 \leq Q \leq 10^5

1 \leq L_i \leq R_i \leq H×W

(R_i-L_i) is a multiple of D.

Input

Input is given from Standard Input in the following format:

H W D
A_{1,1} A_{1,2} ... A_{1,W}
:
A_{H,1} A_{H,2} ... A_{H,W}
Q
L_1 R_1
:
L_Q R_Q

Output

For each test, print the sum of magic points consumed during that test.

Output should be in the order the tests are conducted.

Sample Input 1

3 3 2
1 4 3
2 5 7
8 9 6
1
4 8

Sample Output 1

5

4 is written in Square (1,2).

6 is written in Square (3,3).

8 is written in Square (3,1).

Thus, the sum of magic points consumed during the first test is (|3-1|+|3-2|)+(|3-3|+|1-3|)=5.

Sample Input 2

4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2

Sample Output 2

0
0

Note that there may be a test where the piece is not moved at all, and there may be multiple identical tests.

Sample Input 3

5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13

Sample Output 3

0
5
0



Sample input:
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8


Sample output:
5

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    H, W, D = iip()

    A = iipt(H)
    Q = iip(False)
    LR = iipt(Q)

    position = [None for i in range(H*W)+100]
    for i in range(H):
       for j in range(W):
           n = A[i][j]
           position[n-1] = (i, j)

    distanse = [None for i in range(H*W)+100]
    for i in range(H*W):
        if i+D >= H*W:
            break
        if distanse[i] is None:
            distanse[i] = 0
        distanse[i+D] = distanse[i] + abs(position[i][0]-position[i+D][0]) + abs(position[i][1]-position[i+D][1])

     #print(position)
     #print(distanse)

     for l, r in LR:
         l -= 1
         r -= 1
         print(distanse[r]-distanse[l])


#####################################################ライブラリ集ここから

def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=True):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=False, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left"): # 関数を二分探索
    l = left
    r = right
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if func(x) == target:
            return x
        elif func(x) > target:
            r = x
        else:
            l = x

    if side == "left" or func(x) == target:
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    H, W, D = iip()

    A = iipt(H)
    Q = iip(False)
    LR = iipt(Q)

    position = [None for i in range(H*W)]
    for i in range(H):
       for j in range(W):
           n = A[i][j]
           position[n-1] = (i, j)

    distanse = [None for i in range(H*W)]
    for i in range(H*W):
        if i+D >= H*W:
            break
        if distanse[i] is None:
            distanse[i] = 0
        distanse[i+D] = distanse[i] + abs(position[i][0]-position[i+D][0]) + abs(position[i][1]-position[i+D][1])
    #
    # #print(position)
    # #print(distanse)
    #
    # for l, r in LR:
    #     l -= 1
    #     r -= 1
    #     print(distanse[r]-distanse[l])


#####################################################ライブラリ集ここから

def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=True):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=False, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left"): # 関数を二分探索
    l = left
    r = right
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if func(x) == target:
            return x
        elif func(x) > target:
            r = x
        else:
            l = x

    if side == "left" or func(x) == target:
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    H, W, D = iip()

    A = iipt(H)
    Q = iip(False)
    LR = iipt(Q)

    position = [None for i in range(H*W)]
    for i in range(H):
        for j in range(W):
            n = A[i][j]
            position[n-1] = (i, j)

    next = [None for i in range(H*W)]
    distanse = [None for i in range(H*W)]
    for i in range(H*W):
        if i+D >= H*W:
            break
        if distanse[i] is None:
            distanse[i] = 0
        distanse[i+D] = distanse[i] + abs(position[i][0]-position[i+D][0]) + abs(position[i][1]-position[i+D][1])

    #print(distanse)

    for l, r in LR:
        l -= 1
        r -= 1
        print(distanse[r]-distanse[l])


#####################################################ライブラリ集ここから

def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=True):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=False, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left"): # 関数を二分探索
    l = left
    r = right
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if func(x) == target:
            return x
        elif func(x) > target:
            r = x
        else:
            l = x

    if side == "left" or func(x) == target:
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(H)]
Q=int(input())
X=[[0,0] for _ in range(H*W)]
for i in range(H):
    for j in range(W):
        X[A[i][j]][0]=i
        X[A[i][j]][1]=j
M=[0]*(H*W+1)
for d in range(D+1,H*W+1):
        M[d]=abs(X[d][0]-X[d-D][0])+abs(X[d][1]-X[d-D][1])+M[d-D]

for i in range(Q):
    L,R=map(int,input().split())
    print(M[R]-M[L])

Submission status: Runtime Error

Solution code:
H,W,D = map(int,input().split())

A = [[0]*W for i in range(H)]
data = [0]*(H*W+1)

for i in range(H):
    A[i] = list(map(int,input().split()))

for i in range(H):
    for j in range(W):
        data[A[i][j]] = [i,j]

Q = int(input())

L = [0] * Q
R = [0] * Q

for i in range(Q):
    L[i],R[i] = map(int,input().split())

X = [0]*300

for i in range(D):
    x = H*W-D-i
    count = 0
    while x > 0:
        count += abs(data[x][0]-data[x+D][0])+abs(data[x][1]-data[x+D][1])
        X[x] += count
        x -= D

for i in range(Q):
    print(X[L[i]]-X[R[i]])

Submission status: Runtime Error

Solution code:
def dist(A,a,b):
    ans = [0]*4
    for i in range(W):
        for j in range(H):
            if A[i][j] == a:
                ans[0] = i
                ans[1] = j
            if A[i][j] == b:
                ans[2] = i
                ans[3] = j
    return abs(ans[0]-ans[2])+abs(ans[1]-ans[3])

def exam(L,R,D,A):
    ans = 0
    if L == R:
        return ans
    else:
        while R != L:
            ##print("L",L,"R",R)
            ans += dist(A,L,L+D)
            L += D
        return ans    

H,W,D = map(int,input().split())
A = []
for i in range(H):
    tmp = list(map(int,input().split()))
    A.append(tmp)

LR = []
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    LR.append([L,R])

for i in range(Q):
    print(exam(LR[i][0],LR[i][1],D,A))

Submission status: Runtime Error

Solution code:
H, W, D, *L = map(int, open('0').read().split())
A = L[:W*H]
Q = L[H*W]
inf = []
for l,r in zip(*[iter(L[H*W+1:])]*2):
  inf += [(l,r)]
dic = {A[i*W+j]:(i,j) for i in range(H) for j in range(W)}
ls = [[] for i in range(D)]
for i in range(D):
  s = i if i!=0 else D
  ls[i].append(0)
  m = s
  n = s
  while True:
    n += D
    if H*W<n:
      n = s
    px, py = dic[m]
    x, y = dic[n]
    ls[i].append(ls[i][-1]+abs(px-x)+abs(py-y))
    m = n
    if m==s:
      break
for l, r in inf:
  i = l%D
  if i==0:
    il = (l-D)//D
    ir = (r-D)//D
  else:
    il = (l-i)//D
    ir = (r-i)//D
  if l<r:
    print(ls[i][ir] - ls[i][il])
  elif l>r:
    print(ls[i][-1]-ls[i][il]+ls[i][ir])
  else:
    print(0)

Submission status: Runtime Error

Solution code:
# h*wの1次元配列で各要素に(i,j)のインデックスでもぶちこんどけばやるだけに見えるが
# なぜかTLEなる あとREがあるのはまあ雑にやったからいいとしてなんかしらんけどWAが一つある....

h, w, d = map(int, input().split())
arr = [() for _ in range((h + 1) * (w + 1))]
table = []
for y in range(h):
    line = list(map(int, input().split()))
    arr.append(line)
    for x in range(w):
        arr[line[x]] = (y + 1, x + 1)


for _ in range(int(input())):
    l, r = map(int, input().split())
    ans = 0
    for x in range(l, r, d):
        ans += abs(arr[x][1] - arr[x + d][1]) + abs(arr[y][0] - arr[y + d][0])
    print(ans)

Submission status: Runtime Error

Solution code:
# h*wの1次元配列で各要素に(i,j)のインデックスでもぶちこんどけばやるだけに見えるが
h, w, d = map(int, input().split())
arr = [() for _ in range(h * w + 1)]
table = []
for y in range(h):
    line = list(map(int, input().split()))
    arr.append(line)
    for x in range(w):
        arr[line[x]] = (y + 1, x + 1)


for _ in range(int(input())):
    l, r = map(int, input().split())
    ans = 0
    for x in range(l, r, d):
        ans += abs(arr[x][1] - arr[x + d][1]) + abs(arr[y][0] - arr[y + d][0])
    print(ans)

Submission status: Runtime Error

Solution code:
h,w,d = map(int,input().split())
p = [(0,0)] * (h*w)
c = [0] * (h*w)
for i in range(h):
  a = list(map(int,input().split()))
  for j in range(w):
    p[a[j]-1] = (i,j)

for i in range(d, h*w):
  c[i] = c[i-d] + abs(p[i][0] - p[i-d][0]) + abs(p[i][1] - p[i-d][1])

q = int(input())
ans = 0
for i in range(q):
  l,r = map(int,input().split())
  ans += c[r] - c[l]
print(ans)

Submission status: Runtime Error

Solution code:
h,w,d = list(map(int,input().split(" ")))
numbers = {}
flag = 1
if h==1 and w==1:
    flag = 0

for hh in range(h):
    hh_numbers = list(map(int,input().split(" ")))
    for ww in range(w):
        numbers[hh_numbers[ww]] = [hh,ww]
ruiseki = [[0]*(h*w//d+1) for i in range(d)]  # mod=1,2....,0

for i in range(d):
    if flag == 0:
        break
    for j in range(h*w//d+1):
        bannme = d*j+i+1
        if bannme > h*w:
            break
        ruiseki[i][j] = numbers[bannme]
# print(ruiseki)

ruiseki2 = [[0]*(h*w//d+1) for i in range(d)]
for i in range(d):
    if flag == 0:
        break
    for j in range(len(ruiseki[i])-1):
        ruiseki2[i][j] = abs(ruiseki[i][j+1][1] - ruiseki[i][j][1]) + abs(ruiseki[i][j+1][0] - ruiseki[i][j][0])
# print(ruiseki2)
n = int(input())

ruiseki3 = [[0]*(h*w//d+1) for i in range(d)]
for i in range(d):
    if flag == 0:
        break
    ruiseki3[i][0] = ruiseki2[i][0]
    for j in range(1,len(ruiseki2[i])):
        ruiseki3[i][j] = ruiseki3[i][j-1] + ruiseki2[i][j]
# print(ruiseki3)

for i in range(n):
    if flag == 0:
        print(0)
        continue
    l,r = list(map(int,input().split(" ")))
    if l==r:
        print(0)
        continue
    amari = l%d
    n_l = (l-amari)//d
    n_r = (r-amari)//d
    if amari==0:
        amari=d
        n_l = n_l - 1
        n_r = n_r - 1
    # print(n_l,n_r,amari)
    if n_l == 0:
        print(ruiseki3[amari-1][n_r-1])
        continue
    print(ruiseki3[amari-1][n_r-1]-ruiseki3[amari-1][n_l-1])

Submission status: Runtime Error

Solution code:
h,w,d = list(map(int,input().split(" ")))
numbers = {}
flag = 1
if h==1 and w==1:
    flag = 0

for hh in range(h):
    hh_numbers = list(map(int,input().split(" ")))
    for ww in range(w):
        numbers[hh_numbers[ww]] = [hh,ww]
ruiseki = [[0]*(h*w//d+1) for i in range(d)]  # mod=1,2....,0

for i in range(d):
    if flag == 0:
        break
    for j in range(h*w//d+1):
        bannme = d*j+i+1
        if bannme > h*w:
            break
        ruiseki[i][j] = numbers[bannme]
# print(ruiseki)

ruiseki2 = [[0]*(h*w//d) for i in range(d)]
for i in range(d):
    if flag == 0:
        break
    for j in range(len(ruiseki[i])-1):
        ruiseki2[i][j] = abs(ruiseki[i][j+1][1] - ruiseki[i][j][1]) + abs(ruiseki[i][j+1][0] - ruiseki[i][j][0])
# print(ruiseki2)
n = int(input())

ruiseki3 = [[0]*(h*w//d) for i in range(d)]
for i in range(d):
    if flag == 0:
        break
    ruiseki3[i][0] = ruiseki2[i][0]
    for j in range(1,len(ruiseki2[i])):
        ruiseki3[i][j] = ruiseki3[i][j-1] + ruiseki2[i][j]
# print(ruiseki3)

for i in range(n):
    if flag == 0:
        print(0)
        continue
    l,r = list(map(int,input().split(" ")))
    if l==r:
        print(0)
        continue
    amari = l%d
    n_l = (l-amari)//d
    n_r = (r-amari)//d
    if amari==0:
        amari=d
        n_l = n_l - 1
        n_r = n_r - 1
    # print(n_l,n_r,amari)
    if n_l == 0:
        print(ruiseki3[amari-1][n_r-1])
        continue
    print(ruiseki3[amari-1][n_r-1]-ruiseki3[amari-1][n_l-1])

Submission status: Runtime Error

Solution code:
h,w,d = list(map(int,input().split(" ")))
numbers = {}
flag = 1
if h==1 and w==1:
    flag = 0

for hh in range(h):
    hh_numbers = list(map(int,input().split(" ")))
    for ww in range(w):
        numbers[hh_numbers[ww]] = [hh,ww]
ruiseki = [[0]*(h*w//d+1) for i in range(d)]  # mod=1,2....,0

for i in range(d):
    if flag == 0:
        break
    for j in range(h*w//d+1):
        bannme = d*j+i+1
        if bannme > h*w:
            break
        ruiseki[i][j] = numbers[bannme]
    if ruiseki[i][h*w//d] == 0:
        ruiseki[i].pop()
# print(ruiseki)

ruiseki2 = [[0]*(h*w//d) for i in range(d)]
for i in range(d):
    if flag == 0:
        break
    for j in range(len(ruiseki[i])-1):
        ruiseki2[i][j] = abs(ruiseki[i][j+1][1] - ruiseki[i][j][1]) + abs(ruiseki[i][j+1][0] - ruiseki[i][j][0])
    if ruiseki2[i][h*w//d-1] == 0:
        ruiseki2[i].pop()
# print(ruiseki2)
n = int(input())

ruiseki3 = [[0]*(h*w//d) for i in range(d)]
for i in range(d):
    if flag == 0:
        break
    ruiseki3[i][0] = ruiseki2[i][0]
    for j in range(1,len(ruiseki2[i])):
        ruiseki3[i][j] = ruiseki3[i][j-1] + ruiseki2[i][j]
    if ruiseki3[i][h*w//d-1] == 0:
        ruiseki3[i].pop()
# print(ruiseki3)

for i in range(n):
    print(0)
    continue
    if flag == 0:
        print(0)
        continue
    l,r = list(map(int,input().split(" ")))
    if l==r:
        print(0)
        continue
    amari = l%d
    n_l = (l-amari)//d
    n_r = (r-amari)//d
    if amari==0:
        amari=d
        n_l = n_l - 1
        n_r = n_r - 1
    # print(n_l,n_r,amari)
    if n_l == 0:
        print(ruiseki3[amari-1][n_r-1])
        continue
    print(ruiseki3[amari-1][n_r-1]-ruiseki3[amari-1][n_l-1])