We have a grid with
H rows and
W columns. The square in the
ith row and
jth column will be called
Square(i, j). Integers from
1 to
H·W are written over the entire grid, and an integer written in
Square(i, j) is equal to
Ai,j.
You are a wizard and can teleport a shape placed on
Square(i, j) to
Square(x, y) by spending
\(|x-i|+|y-j|\) magiks (magic coins).
Now you need to pass
Q practice tests on your abilities as a wizard (sorceress).
Ith test will be conducted as follows:
- initially the figure is located in the square, where the integer is written
Li;
- Let
x be the integer written in the square occupied by the shape. Repeatedly move the shape to the square where the integer
x+D is written until
x will not become equal to
Ri. The test ends when
x =
Ri .
It is guaranteed that
Ri-
Li is divisible by
D.
For each test, find the sum of magics consumed during that test.
Input
The first line contains three integers: H, W and D (\( 1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
The following H lines contain W numbers Ai,j (\(1 \leq A_{i,j} \leq H \cdot W\), \(A_{i,j} \ neq A_{x,y} ((i,j) \neq (x,y))\).
The next line contains an integer Q (\(1 \leq Q \leq 10^5\)).
The last Q lines contain 2 integers each: Li and Ri (\(1 \leq L_i \leq R_i \leq H \cdot W\)), \((R_i-L_i)\) multiple of D.
Imprint
For each test, print the sum of magics spent during this test. The output should be in the order of the tests.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
3 3 2
1 4 3
2 5 7
8 9 6
1
48 |
5 |
- 4 is written as Square(1,2).
- 6 is in Square(3,3).
- 8 is written in Square (3,1).
Thus, the sum of magic points spent during one test is:
\((|3-1|+|3-2|)+(|3-3|+|1-3|)=5\).
|
| 2 |
4 2 3
37
14
5 2
68
2
2 2
2 2 |
0
0 |
Note that there may be a test where the shape doesn't move at all, and there may be multiple identical tests. |
| 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
| 0
5
0 |
|