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:
Python 3.5.1 (v3.5.1:37a07cee5969, Dec  6 2015, 01:54:25) [MSC v.1900 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
8
P Y W G Y W Y Y

Four
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
8
P Y W G Y W Y Y
Four
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
9
G W W G P W P G G
Three
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI
5
['MASHIKE', 'RUMOI', 'OBIRA', 'HABORO', 'HOROKANAI']
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI
13
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI
[1, 0, 1, 0, 2]
1 0 1 0
1 0 0 0
1 0 2 0
1 1 1 1
1 1 0 1
1 1 2 3
1 0 1 3
1 0 0 3
1 0 2 3
1 2 1 5
1 2 0 5
1 2 2 9
0 1 0 9
0 1 2 9
0 0 0 9
0 0 2 9
0 2 0 9
0 2 2 9
1 0 2 9
1 2 2 13
13
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI
[1, 0, 1, 0, 2]
[1, 1, 0, 2]
1 1 0 0
1 1 2 2
1 0 0 2
1 0 2 2
1 2 0 2
1 2 2 6
1 0 2 6
1 2 2 10
10
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI
[1, 0, 1, 0, 2]
[1, 1, 2]
1 1 2 2
1 2 2 6
6
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI
[1, 0, 1, 0, 2]
[1, 1, 2]
1 1 2 : 2
1 2 2 : 6
6
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI
[1, 0, 1, 0, 2]
[1, 1, 2]
1 1 2 : 2
1 2 2 : 6
6
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
        cnt2=cnt1+1

Traceback (most recent call last):
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py", line 1, in <module>
    n=int(input())
ValueError: invalid literal for int() with base 10: '        cnt2=cnt1+1'
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI
[1, 0, 1, 0, 2]
[1, 1, 2]
1 1 2 : 2
2
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
4
ZZ
ZZZ
Z
ZZZZZZZZZZ
[0, 0, 0, 0, 0]
[]
0
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
5
CHOKUDAI
RNG
MAKOTO
AOKI
RINGO
[1, 1, 2, 1, 0]
[1, 1, 2, 1]
1 1 2 : 2
1 1 1 : 3
1 2 1 : 5
1 2 1 : 7
7
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
5
CHOKUDAI
RNG
MAKOTO
AOKI
RINGO
7
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
Traceback (most recent call last):
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py", line 4, in <module>
    a.append(list(map(int, input(split()))))
NameError: name 'split' is not defined
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
3 3 2
[[1, 4, 3], [2, 5, 7], [8, 9, 6]]
1
[[4, 8]]
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
[4]
[8]
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2
[2, 2]
[2, 2]
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
Traceback (most recent call last):
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py", line 15, in <module>
    print(a.index(4))
ValueError: 4 is not in list
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
Traceback (most recent call last):
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py", line 15, in <module>
    print(a.index(3))
ValueError: 3 is not in list
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
Traceback (most recent call last):
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py", line 20, in <module>
    inw = a.index(x+d)
ValueError: 6 is not in list
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
Traceback (most recent call last):
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py", line 20, in <module>
    inw = a[inh].index(x+d)
ValueError: 6 is not in list
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
Traceback (most recent call last):
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py", line 21, in <module>
    inw = a[inh].index(x+d)
ValueError: 6 is not in list
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
[2, 5, 7]
[8, 9, 6]
Traceback (most recent call last):
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py", line 20, in <module>
    print(a[inh])
IndexError: list index out of range
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
            print(a[inh])

Traceback (most recent call last):
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py", line 1, in <module>
    h,w,d=map(int, input().split())
ValueError: invalid literal for int() with base 10: 'print(a[inh])'
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
[1, 4, 3]
[2, 5, 7]
[8, 9, 6]
Traceback (most recent call last):
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py", line 19, in <module>
    print(a[inh])
IndexError: list index out of range
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2 2
[1, 4, 3]
2Traceback (most recent call last):
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py", line 22, in <module>
    print(inh, inw)
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\lib\idlelib\PyShell.py", line 1344, in write
    return self.shell.write(s, self.tags)
KeyboardInterrupt
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
[1, 4, 3]
2 2
[1, 4, 3]
2 0
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
Traceback (most recent call last):
  File "C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py", line 17, in <module>
    while l[i] not in a[inh]:
NameError: name 'inh' is not defined
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8
3
5
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
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
4
5
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
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
0
5
0
>>> 
 RESTART: C:\Users\Yutaka\AppData\Local\Programs\Python\Python35\myfiles\abc.py 
4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2
0
0
>>>

Submission status: Runtime Error

Solution code:
def solve():
    h, w, d = map(int, input().split())

    a = [(0,0) for i in range(h*w+1)]
    for y in range(h):
        row = list(map(int, input().split()))
        for x, v in enumerate(row):
            a[v] = (x, y)

    q = int(input())

    l, r = [], []

    for i in range(q):
        l_, r_ = map(int, input().split())
        l.append(l_)
        r.append(r_)

    # print(h, w, d)
    # print(a)
    # print(l, r)

    from collections import defaultdict
    memo = defaultdict(int)
    memoto = [h*w+1 for i in range(h*w+1)]

    def magic(fr, to, d, m):
        if to-fr == 0:
            return 0

        if (to-fr) // d == 1:
            frx, fry = a[fr]
            tox, toy = a[to]
            dist = abs(frx-tox) + abs(fry-toy)
            return m + dist

        else:

            last = memo[(to - d, to)]
            if last == 0:
                last = magic(to - d, to, d, m)
                memo[(to - d, to)] = last
                memoto[to] = min(memoto[to], to - d)

            rest = memo[(fr, to-d)]
            if rest == 0:
                rest = magic(fr, to-d, d, m)
                memo[(fr, to - d)] = rest
                memoto[to-d] = min(memoto[to-d], fr)
            return last + rest

    for qi in range(q):
        l_ = l[qi]
        r_ = r[qi]
        # print(memoto)
        # print(l_, r_)
        if memoto[r_] < r_ and memoto[r_] >= l_:
            ans = memo[(memoto[r_], r_)] + magic(l_, memoto[r_], d, 0)
        elif memoto[r_] < r_ and memoto[r_] <= l_:
            ans = memo[(memoto[r_], r_)] - magic(memoto[r_], l_, d, 0)
        else:
            ans = magic(l[qi], r[qi], d, 0)
        print(ans)

solve()

Submission status: Runtime Error

Solution code:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

def search_index(num, arr, height):
	for i in range(height):
		if num in arr[i]:
			return i,arr[i].index(num)
	return -1,-1

maryoku = 0
for i in range(Q):
	ori_i,ori_j = search_index(LR[i][0], A, H)
	x = A[ori_i][ori_j]
	for i in range(LR[i][1] - LR[i][0])
		x += D
		tra_i,tra_j = search_index(x, A, H)
		maryoku += abs(tra_i-ori_i) + abs(tra_j-ori_j)
		ori_i, ori_j = tra_i, tra_j
print maryoku

Submission status: Runtime Error

Solution code:
def ACBC_089_D():
    _hwd = str(input()).split()
    _hwd = list(map(int, _hwd))
    _area = []
    _inifin = []
    _mpcount = 0

    for i in range(0, _hwd[0]):
        _aij = str(input()).split()
        _aij = list(map(int, _aij))
        _area += _aij

    _q = int(input())
    for i in range(0, _q):
        _lrq = str(input().split())
        _lrq = list(map(int, _lrq))
        for i in range(0, _hwd[0]):
            if _lrq[0] in _area[i]:
                _inix = _area[i].index(_lrq[0])
                _iniy = i
            if _lrq[1] in _area[i]:
                _finx = _area[i].index(_lrq[1])
                _finy = i
        _nowx = _inix
        _nowy = _iniy
        for i in range(0, int((_lrq[1]-_lrq[0])/_hwd[2])):
            for i in range(1, _hwd[0]+1):
                if _lrq[0]+_hwd[2]*i in _area[i]:
                    _nowx = _area[i].index(_lrq[0]+_hwd[2]*i)
                    _nowy = i
                _mpcount += _nowx+_nowy-_inix-_iniy 
                
        print(_mpcount)

ACBC_089_D()

Submission status: Runtime Error

Solution code:
h,w,d=[int(i) for i in input().split()]
p=[[-1,-1] for i in range(h*w+1) ]
a=[]
for i in range(h):
  a0 =[int(i0) for i0 in input().split()]
  a.append(a0)
  for j in range(w):
    p[a0[j]]=[i,j]

n=int(input())

import sys
sys.setrecursionlimit(100000)
from functools import lru_cache

@lru_cache(maxsize=3000)
def dist_d(s,g,d,y0,x0):
  if s==g:
    return 0
  else:
    s = s+d
    y,x = p[s]
    return abs(x-x0)+abs(y-y0) + dist_d(s,g,d,y,x)
  
for i in range(n):
  z=0
  s,g=[int(i0) for i0 in input().split()]
  y0,x0=p[s]
  print(dist_d(s,g,d,y0,x0))

Submission status: Runtime Error

Solution code:
import numpy as np
in1=list(map(int,input().split(" ")))
#print(in1)
#arr=np.zeros((in1[0],in1[1]))
d={}
for i in range(in1[0]):
    #arr[i]=input().split(" ")
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]
#print(arr)
Q=int(input())
test=[]
out=[]
route=[]
for k in range(Q):
    ans=0
    start,end=list(map(int,input().split(" ")))
    #place=np.where(arr==start)
    place=d[start]
    #print(start,end)
    while start != end:
        #print("ans",ans)
        #nextplace=np.where(arr==start+in1[2])#[1][0]
        if start in route:
            nextplace=d[start+in1[2]]
        else:
            nextplace=d[start+in1[2]]
            ans1=abs(int(nextplace[0])-int(place[0]))
            ans2=abs(int(nextplace[1])-int(place[1]))
            route[start]=ans1+ans2
        ans+=route[start]
        start+=in1[2]
        place=nextplace

    print(ans)
    #out.append(ans)
#for i in out:
    #print(i)

Submission status: Runtime Error

Solution code:

H,W,D=map(int,input().split())
A=[]
for i in range(H):
    A.extend(list(map(int,input().split())))
Q=int(input())
LR=[]
for _ in range(Q):
	LR.append(tuple(map(int,input().split())))

for l,r in LR:
	ans=0
	sx,sy=divmod(A.index(l),W)
	while A[sx*W+sy]!=r:
		tx,ty=divmod(A.index(l+D),H)
		ans+=abs(tx-sx)+abs(sy-ty)
		l+=D
		sx,sy=tx,ty
	print(ans)

Submission status: Runtime Error

Solution code:
b = str(input()).split()
h = int(b[0])
w = int(b[1])
d = int(b[2])
c =[]

def abs(a,b):
    if a > b:
        return(a-b)
    else:
        return(b-a)

for i in range(0,h):
    c.append(str(input()).split())

q = int(input())
lr = []
energy = 0



for i in range(0,q):
    lr.append(str(input()).split())

for i in range(0,q):
    l = int(lr[i][0])
    r = int(lr[i][1])
    for j in range(0,h):
        for k in range(0,w):
            if int(c[j][k]) == l:
                li = j
                lj = k
            if int(c[j][k]) == l + d:
                di = j
                dj = k
        if l != r:
            energy += abs(li,di) + abs(lj,dj)
            l += d
        else:
            print(energy)
            break

Submission status: Runtime Error

Solution code:

H, W, D = [int(x) for x in input().strip().split(' ')]
stage = {}
for i in range(H):
    nums = [int(x) for x in input().strip().split(' ')]
    for j in range(W):
        stage[nums[j]] = [i + 1, j + 1]
Q = int(input())
tests = []
for _ in range(Q):
    tests.append([int(x) for x in input().strip().split(' ')])

scores = []
done = {}
for i in range(Q):
    L, R = tests[i]
    if (L, R) in done:
        scores.append(done[(L, R)])
    elif L == R:
        scores.append(0)
    else:
        x, y = stage[L]
        score = 0
        while L < R:
            if (L, R) in done:
                score += done[(L, R)]
                break
            new_x, new_y = stage[L + D]
            del stage[L + D]
            score += abs(new_x - x) + abs(new_y - y)
            x = new_x
            y = new_y
            L += D
        scores.append(score)
        done[(L, R)] = score

for score in scores:
    print(score)

Submission status: Runtime Error

Solution code:
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())

H,W,D = Is()
d = dict()
for i in range(H):
    s = Is()
    for j,e in enumerate(s):
        d[e] = (i,j)
Q = I()

m = [[0]*H*W for i in range(H*W)] 
def calc(l,r):
    if m[l][r] != 0:
        return m[l][r]
    else:
        maho = abs(d[l+D][0] - d[l][0]) + abs(d[l+D][1] - d[l][1])
        m[l][l+D] = maho
        return maho
    
for q in range(Q):
    l,r = Is()
    maho = 0
    for k in range(l,r,D):
        maho += calc(k,r)
#        print(k,r,maho)
    print(maho)

Submission status: Runtime Error

Solution code:

H, W, D = [int(x) for x in input().strip().split(' ')]
stage = {}
for i in range(H):
    nums = [int(x) for x in input().strip().split(' ')]
    for j in range(W):
        stage[nums[j]] = [i + 1, j + 1]
Q = int(input())
tests = []
for _ in range(Q):
    tests.append([int(x) for x in input().strip().split(' ')])

scores = []
done = {}
for i in range(Q):
    L, R = tests[i]
    if (L, R) in done:
        scores.append(done[[L, R]])
    elif L == R:
        scores.append(0)
    else:
        x, y = stage[L]
        score = 0
        while L < R:
            if (L, R) in done:
                score += done[(L, R)]
                break
            new_x, new_y = stage[L + D]
            del stage[L + D]
            score += abs(new_x - x) + abs(new_y - y)
            x = new_x
            y = new_y
            L += D
        scores.append(score)
        done[(L, R)] = score

for score in scores:
    print(score)

Submission status: Runtime Error

Solution code:
h,w,d=[int(i) for i in input().split()]
p=[[-1,-1] for i in range(h*w+1) ]
a=[]
for i in range(h):
  a0 =[int(i0) for i0 in input().split()]
  a.append(a0)
  for j in range(w):
    p[a0[j]]=[i,j]

n=int(input())

import sys
sys.setrecursionlimit(100000)
from functools import lru_cache

@lru_cache(maxsize=None)
def dist_d(s,g,d):
  if s==g:
    return 0
  else:
    y0,x0=p[s]
    s = a[y0][x0]+d
    y,x = p[s]
    return abs(x-x0)+abs(y-y0) + dist_d(s,g,d)
  
for i in range(n):
  z=0
  s,g=[int(i0) for i0 in input().split()]
 
  print(dist_d(s,g,d))

Submission status: Runtime Error

Solution code:
import numpy as np


def move_and_compute_cost(field, h, d, l, r):
    if l == r:
        return 0

    ff = field.ravel()
    # create l to r route
    route = np.arange(l, r + 1, d)

    indices = np.arange(len(ff))
    cond = np.isin(ff, route)

    indices = indices[cond]
    ff = ff[cond]
    v = indices[ff.argsort()]

    points = np.vstack([v // h, v % h]).T
    next_points = np.vstack([points[1:], points[-1]])

    cost = np.abs(points - next_points).sum()
    return cost


if __name__ == '__main__':
    h, w, d = [int(v) for v in input().split()]

    # read field
    field = np.empty((h, w), dtype=int)
    for i in range(h):
        line = [int(v) for v in input().split()]
        field[i, :] = line

    ls, rs = [], []
    q = int(input())
    for i in range(q):
        line = [int(v) for v in input().split()]
        ls.append(line[0])
        rs.append(line[1])

    costs = [move_and_compute_cost(field, h, d, l, r) for l, r in zip(ls, rs)]
    for c in costs:
        print(c)

Submission status: Runtime Error

Solution code:

H, W, D = [int(x) for x in input().strip().split(' ')]
stage = {}
for i in range(H):
    nums = [int(x) for x in input().strip().split(' ')]
    for j in range(W):
        stage[nums[j]] = [i + 1, j + 1]
Q = int(input())
tests = []
for _ in range(Q):
    tests.append([int(x) for x in input().strip().split(' ')])

scores = []
done = {}
for i in range(Q):
    L, R = tests[i]
    if (L, R) in done:
        scores.append(done[[L, R]])
    elif L == R:
        scores.append(0)
    else:
        x, y = stage[L]
        score = 0
        while L < R:
            new_x, new_y = stage[L + D]
            score += abs(new_x - x) + abs(new_y - y)
            x = new_x
            y = new_y
            L += D
        scores.append(score)
        done[(L, R)] = score

for score in scores:
    print(score)

Submission status: Runtime Error

Solution code:
H, W, D = map(int, input().split())
A = [[] * W for i in range(H)]
dic = {}
for i in range(H):
    a = list(map(int, input().split()))
    A[i] = a
    for j in range(W):
        dic[a[j]] = (i + 1, j + 1)

rec = {}


def cal(L, R):
    global rec
    if L == R:
        return 0
    if (L, R) in rec:
        return rec[(L, R)]
    else:
        p = abs(dic[L + D][0] - dic[L][0]) + abs(dic[L + D][1] - dic[L][1])
        rec[(L, L + D)] = p
        rec[(L + D, R)] = cal(L + D, R)
        rec[(L, R)] = rec[(L, L + D)] + rec[(L + D, R)]
        return rec[(L, R)]


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

Submission status: Runtime Error

Solution code:
temp = list(map(int,input().split()))
H = temp[0]
W = temp[1]
D = temp[2]
dic = [0 for x in range(H*W)]
for i in range(H):
    temp = list(map(int,input().split()))
    for j in range(len(temp)):
        ad = [str(i),str(j)]
        key = " ".join(ad)
        dic[temp[j]-1] = key

Q = int(input())
end = {}
for i in range(Q):
    tot = input().split()
    temp = list(map(int,tot))
    L = temp[0]
    R = temp[1]
    literature = " ".join(tot)
    length = 0
    if L == R:
        print(0)
    elif literature in end.keys():
        print(int(end[literature]))
    else:
        Lt = L
        for j in range(int((R-L)/D)):
            pre = list(map(int,dic[Lt].split()))
            pro = list(map(int,dic[Lt+D].split()))
            length += abs(pre[0]-pro[0]) + abs(pre[1]-pro[1])
            Lt = Lt+D
        print(length)
        end[literature] = str(length)