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