У нас есть сетка с
H строками и
W столбцами. Квадрат в
i-й строке и
j-м столбце будет называться
Square(i, j). Целые числа от
1 до
H·W записаны по всей сетке, а целое число, записанное в
Square(i, j), равно
Ai,j.
Вы - волшебник (волшебница), и можете телепортировать фигуру, помещенную на
Square(i, j) в
Square(x, y), потратив
\(|x-i|+|y-j|\) маджиков (магических монет).
Теперь вам нужно пройти
Q практических тестов на свои способности как волшебника (волшебницы).
I-е испытание будет проводиться следующим образом:
- первоначально фигура располагается в квадрате, где записано целое число
Li;
- пусть
x будет целым числом, записанным в квадрате, занятом фигурой. Неоднократно переместите фигуру в квадрат, где написано целое число
x+D, пока
x не станет равен
Ri. Тест заканчивается, когда
x =
Ri .
Гарантируется, что
Ri-
Li делится на
D.
Для каждого теста найдите сумму маджиков, израсходованных во время этого теста.
Входные данные
В первой строке заданы три целых числа:
H,
W и
D (
\(1\leq H,W \leq 300\),
\(1 \leq D \leq H \cdot W\)).
В следующих
H строках записано по
W чисел
Ai,j (
\(1 \leq A_{i,j} \leq H \cdot W\),
\(A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))\).
В следующей строке записано целое число
Q (
\(1 \leq Q \leq 10^5\)).
В последних Q строках записано по 2 целых числа:
Li и
Ri (
\(1 \leq L_i \leq R_i \leq H \cdot W\)),
\((R_i-L_i)\) кратно
D.
Выходные данные
Для каждого теста выведите сумму маджиков, израсходованных во время этого теста. Вывод должен быть в порядке проведения тестов.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8 |
5 |
- 4 записано Square (1,2).
- 6 записано в Square (3,3).
- 8 записано in Square (3,1).
Таким образом, сумма магических очков, израсходованных во время одного теста, составляет:
\((|3-1|+|3-2|)+(|3-3|+|1-3|)=5\).
|
| 2 |
4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2 |
0
0 |
Обратите внимание, что может быть тест, в котором фигура вообще не перемещается, и может быть несколько идентичных тестов. |
| 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 |
|