Джабер супергерой в большой стране, которая может быть представлена как таблица с \(n\) строками и \(m\) столбцами, где в каждой клетке этой таблицы находится свой город.
Джабер дал каждому городу в стране свой цвет от \(1\) до \(k\). За одну секунду он может пройти из текущего города в любой соседний по стороне город или в любой город, с таким же цветом, как цвет текущего города.
Джабер должен выполнить \(q\) миссий. В каждой миссии он начинает в городе в строке \(r_1\) и столбце \(c_1\) и должен помочь кому-то в городе в строке \(r_2\) и столбце \(c_2\).
Джабер просит вашей помощи в расчете минимального возможного времени, необходимого, чтобы попасть из стартового города в конечный в каждой миссии.
Выходные данные
Для каждой миссии выведите минимальное время, необходимое, чтобы попасть в клетку \((r_2, c_2)\), начав в клетке \((r_1, c_1)\).
Примечание
В первом тесте:
- миссия \(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)\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
|
2
|
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
|