D. Три фигуры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы наткнулись на новый вид шахматной головоломки. Доска, на которой вы играете, не обязательно $$$8 \times 8$$$, но обязательно $$$N \times N$$$. На каждой клетке записано некоторое число от $$$1$$$ до $$$N^2$$$, и все числа попарно различны. В $$$j$$$-й клетке $$$i$$$-й строки записано число $$$A_{ij}$$$.

У вас в распоряжении только три фигуры: конь, слон и ладья. Вначале вы выставляете одну из фигур в клетку с номером $$$1$$$ (вы сами выбираете какую). Далее вы хотите добраться до клетки с номером $$$2$$$ (возможно, проходя через некоторые другие клетки в процессе), далее — до клетки $$$3$$$ и так далее, пока не достигнете клетки $$$N^2$$$. За один шаг вы можете либо сделать один валидный ход текущей фигурой, либо заменить фигуру на другую в вашем распоряжении. Каждая клетка может быть посещена любое количество раз.

Конь может ходить на две клетки по горизонтали и одну по вертикали, либо на две клетки по вертикали и одну по горизонтали. Слон двигается по диагонали. Ладья движется по вертикали или горизонтали. Во время хода фигуры она должна переместиться в клетку, отличную от текущей.

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

Найдите путь, отвечающий всем условиям.

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

Первая строка содержит одно число $$$N$$$ ($$$3 \le N \le 10$$$) — размер шахматной доски.

Каждая из следующих $$$N$$$ строк содержит $$$N$$$ чисел $$$A_{i1}, A_{i2}, \dots, A_{iN}$$$ ($$$1 \le A_{ij} \le N^2$$$) — числа, написанные на клетках $$$i$$$-й строки доски.

Гарантируется, что все $$$A_{ij}$$$ попарно различны.

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

В единственной строке выведите два числа — количество шагов в лучшем ответе и количество замен в нем.

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

Один из оптимальных ответов описан ниже (начальная фигура — конь):

  1. Перейти в $$$(3, 2)$$$
  2. Перейти в $$$(1, 3)$$$
  3. Перейти в $$$(3, 2)$$$
  4. Заменить коня на ладью
  5. Перейти в $$$(3, 1)$$$
  6. Перейти в $$$(3, 3)$$$
  7. Перейти в $$$(3, 2)$$$
  8. Перейти в $$$(2, 2)$$$
  9. Перейти в $$$(2, 3)$$$
  10. Перейти в $$$(2, 1)$$$
  11. Перейти в $$$(1, 1)$$$
  12. Перейти в $$$(1, 2)$$$