time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You stumbled upon a new kind of chess puzzles. The chessboard you are given is not necesserily $\mathrm{8\times 88\times 8,\; but\; it\; still\; is N\times NN\times N.\; Each\; square\; has\; some\; number\; written\; on\; it,\; all\; the\; numbers\; are\; from 11 to N2N2 and\; all\; the\; numbers\; are\; pairwise\; distinct.\; The jj-th\; square\; in\; the ii-th\; row\; has\; a\; number AijAij 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 $\mathrm{11(you\; can\; choose\; which\; one).\; Then\; you\; want\; to\; reach\; square 22 (possibly\; passing\; through\; some\; other\; squares\; in\; process),\; then\; square 33and\; so\; on\; until\; you\; reach\; square N2N2.\; 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 $\mathrm{NN (3\le N\le 103\le N\le 10)\; —\; the\; size\; of\; the\; chessboard.}$

Each of the next $\mathrm{NN lines\; contains NN integers Ai1,Ai2,\dots ,AiNAi1,Ai2,\dots ,AiN (1\le Aij\le N21\le Aij\le N2)\; —\; the\; numbers\; written\; on\; the\; squares\; of\; the ii-th\; row\; of\; the\; board.}$

It is guaranteed that all ${\mathrm{AijAij 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

Copy

3 1 9 3 8 6 7 4 2 5

output

Copy

12 1

Note

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

1. Move to $(3,2)(3,2)$
2. Move to $(1,3)(1,3)$
3. Move to $(3,2)(3,2)$
4. Replace the knight with a rook
5. Move to $(3,1)(3,1)$
6. Move to $(3,3)(3,3)$
7. Move to $(3,2)(3,2)$
8. Move to $(2,2)(2,2)$
9. Move to $(2,3)(2,3)$
10. Move to $(2,1)(2,1)$
11. Move to $(1,1)(1,1)$
12. Move to $(1,2)$

1 #include
       
          2 using namespace std;  3 #define F(i,a,b) for(int i=a;i<=b;i++)   4 #define D(i,a,b) for(int i=a;i>=b;i--)   5 #define ms(i,a)  memset(a,i,sizeof(a))   6 #define LL       long long   7 template
        
         void read(T &x){  8     x=0; char c=getchar();   9     while (!isdigit(c)) c=getchar(); 10     while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();  11 } 12 template
         
          void write(T x){ 13     if(x>9) write(x/10);  14     putchar(48+x%10);  15 } 16 template
          
           void writeln(T x){ 17     write(x);  18     putchar('\n');  19 } 20 template
           
            void chkmin(T &x,T y){
     if(x==-1) x=y;else x=x
            
             -1) chkmin(d[g][k+1][jj][p],d[i][k][jj][j]+t[i][g][p]+1); 38 } 39 } 40 F(j,0,n*n) F(k,0,2){ 41 if(f[x][j][k]==-1) continue; 42 F(p,0,2) F(g,0,n*n)if(j+g<=n*n && d[x+1][g][k][p]>-1) chkmin(f[x+1][j+g][p],f[x][j][k]+d[x+1][g][k][p]); 43 } 44 } 45 46 void bfs(){ 47 ms(-1,t); 48 int r=0; 49 F(i,1,n*n)F(j,0,2){ 50 q[++r]=i;q[++r]=i;q[++r]=j; 51 t[i][i][j]=0; 52 } 53 F(i,1,r){ 54 int a=q[i]; 55 int b=q[i+1]; 56 int c=q[i+2]; 57 i+=2; 58 if(c==0){ 59 F(p,0,7){ 60 int tx=x[b]+dx[p]; 61 int ty=y[b]+dy[p]; 62 if(tx<1 || ty<1 || tx>n || ty>n) continue; 63 int nv=num[tx][ty]; 64 if(t[a][nv][c]==-1){ 65 t[a][nv][c]=t[a][b][c]+1; 66 q[++r]=a;q[++r]=nv; q[++r]=c; 67 } 68 } 69 } 70 if(c==1){ 71 F(p,0,3) F(k,1,n){ 72 int tx=x[b]+ex[p]*k; 73 int ty=y[b]+ey[p]*k; 74 if(tx<1 || ty<1 || tx>n || ty>n) break; 75 int nv=num[tx][ty]; 76 if(t[a][nv][c]==-1){ 77 t[a][nv][c]=t[a][b][c]+1; 78 q[++r]=a;q[++r]=nv;q[++r]=c; 79 } 80 } 81 } 82 if(c==2){ 83 F(p,0,3) F(k,1,n){ 84 int tx=x[b]+cx[p]*k; 85 int ty=y[b]+cy[p]*k; 86 if(tx<1 || ty<1 || tx>n || ty>n) break; 87 int nv=num[tx][ty]; 88 if(t[a][nv][c]==-1){ 89 t[a][nv][c]=t[a][b][c]+1; 90 q[++r]=a; q[++r]=nv; q[++r]=c; 91 } 92 } 93 } 94 } 95 } 96 97 int main(){ 98 read(n); 99 F(i,1,n) F(j,1,n){100 read(num[i][j]);101 x[num[i][j]]=i; 102 y[num[i][j]]=j; 103 } 104 bfs(); 105 ms(-1,f); 106 f[1][0][0]=0; 107 f[1][0][1]=0; 108 f[1][0][2]=0; 109 F(i,1,n*n-1) init(i); 110 int ans=100000000; 111 int cnt; 112 F(j,0,n*n) F(k,0,2) {113 if(f[n*n][j][k]==-1) continue; 114 if(f[n*n][j][k]