F. Супер Джабер
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джабер супергерой в большой стране, которая может быть представлена как таблица с $$$n$$$ строками и $$$m$$$ столбцами, где в каждой клетке этой таблицы находится свой город.

Джабер дал каждому городу в стране свой цвет от $$$1$$$ до $$$k$$$. За одну секунду он может пройти из текущего города в любой соседний по стороне город или в любой город, с таким же цветом, как цвет текущего города.

Джабер должен выполнить $$$q$$$ миссий. В каждой миссии он начинает в городе в строке $$$r_1$$$ и столбце $$$c_1$$$ и должен помочь кому-то в городе в строке $$$r_2$$$ и столбце $$$c_2$$$.

Джабер просит вашей помощи в расчете минимального возможного времени, необходимого, чтобы попасть из стартового города в конечный в каждой миссии.

Входные данные

В первой строке находится три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq n, m \leq 1000$$$, $$$1 \leq k \leq min(40 , n \cdot m)$$$) — количество строк, столбцов и цветов.

Каждая из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел. В $$$i$$$-й строке, $$$j$$$-е число это $$$a_{ij}$$$ ($$$1 \leq a_{ij} \leq k$$$), оно равно цвету, данному городу в строке $$$i$$$ и столбце $$$j$$$.

В следующей строке находится единственное целое число $$$q$$$ ($$$1 \leq q \leq 10^{5}$$$)  — количество миссий.

В каждой из следующих $$$q$$$ строк находится четыре целых числа $$$r_1$$$, $$$c_1$$$, $$$r_2$$$, $$$c_2$$$ ($$$1 \leq r_1 , r_2 \leq n$$$, $$$1 \leq c_1 , c_2 \leq m$$$)  — координаты начального и конечного городов для очередной миссии.

Гарантируется, что для каждого цвета между $$$1$$$ и $$$k$$$ существует хотя бы один город с таким цветом.

Выходные данные

Для каждой миссии выведите минимальное время, необходимое, чтобы попасть в клетку $$$(r_2, c_2)$$$, начав в клетке $$$(r_1, c_1)$$$.

Примеры
Входные данные
3 4 5
1 2 1 3
4 4 5 5
1 2 1 3
2
1 1 3 4
2 2 2 2
Выходные данные
2
0
Входные данные
4 4 8
1 2 2 8
1 3 4 7
5 1 7 6
2 3 8 8
4
1 1 2 2
1 1 3 4
1 1 2 4
1 1 4 4
Выходные данные
2
3
3
4
Примечание

В первом тесте:

  • миссия $$$1$$$: Джабер должен пойти из клетки $$$(1,1)$$$ в клетку $$$(3,3)$$$ потому что они одинакового цвета, затем из клетки $$$(3,3)$$$ в клетку $$$(3,4)$$$ потому что они соседние по стороне (всего два хода);
  • миссия $$$2$$$: Джабер уже начинает в конечной клетке.

Во втором тесте:

  • миссия $$$1$$$: $$$(1,1)$$$ $$$\rightarrow$$$ $$$(1,2)$$$ $$$\rightarrow$$$ $$$(2,2)$$$;
  • миссия $$$2$$$: $$$(1,1)$$$ $$$\rightarrow$$$ $$$(3,2)$$$ $$$\rightarrow$$$ $$$(3,3)$$$ $$$\rightarrow$$$ $$$(3,4)$$$;
  • миссия $$$3$$$: $$$(1,1)$$$ $$$\rightarrow$$$ $$$(3,2)$$$ $$$\rightarrow$$$ $$$(3,3)$$$ $$$\rightarrow$$$ $$$(2,4)$$$;
  • миссия $$$4$$$: $$$(1,1)$$$ $$$\rightarrow$$$ $$$(1,2)$$$ $$$\rightarrow$$$ $$$(1,3)$$$ $$$\rightarrow$$$ $$$(1,4)$$$ $$$\rightarrow$$$ $$$(4,4)$$$.