Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Three Pieces

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou stumbled upon a new kind of chess puzzles. The chessboard you are given is not necesserily $$$8 \times 8$$$, but it still is $$$N \times N$$$. Each square has some number written on it, all the numbers are from $$$1$$$ to $$$N^2$$$ and all the numbers are pairwise distinct. The $$$j$$$-th square in the $$$i$$$-th row has a number $$$A_{ij}$$$ written on it.

In your chess set you have only three pieces: a knight, a bishop and a rook. At first, you put one of them on the square with the number $$$1$$$ (you can choose which one). Then you want to reach square $$$2$$$ (possibly passing through some other squares in process), then square $$$3$$$ and so on until you reach square $$$N^2$$$. In one step you are allowed to either make a valid move with the current piece or replace it with some other piece. Each square can be visited arbitrary number of times.

A knight can move to a square that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally. A bishop moves diagonally. A rook moves horizontally or vertically. The move should be performed to a different square from the one a piece is currently standing on.

You want to minimize the number of steps of the whole traversal. Among all the paths to have the same number of steps you want to choose the one with the lowest number of piece replacements.

What is the path you should take to satisfy all conditions?

Input

The first line contains a single integer $$$N$$$ ($$$3 \le N \le 10$$$) — the size of the chessboard.

Each of the next $$$N$$$ lines contains $$$N$$$ integers $$$A_{i1}, A_{i2}, \dots, A_{iN}$$$ ($$$1 \le A_{ij} \le N^2$$$) — the numbers written on the squares of the $$$i$$$-th row of the board.

It is guaranteed that all $$$A_{ij}$$$ are pairwise distinct.

Output

The only line should contain two integers — the number of steps in the best answer and the number of replacement moves in it.

Example

Input

3

1 9 3

8 6 7

4 2 5

Output

12 1

Note

Here are the steps for the first example (the starting piece is a knight):

- Move to $$$(3, 2)$$$
- Move to $$$(1, 3)$$$
- Move to $$$(3, 2)$$$
- Replace the knight with a rook
- Move to $$$(3, 1)$$$
- Move to $$$(3, 3)$$$
- Move to $$$(3, 2)$$$
- Move to $$$(2, 2)$$$
- Move to $$$(2, 3)$$$
- Move to $$$(2, 1)$$$
- Move to $$$(1, 1)$$$
- Move to $$$(1, 2)$$$

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/24/2020 02:01:15 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|