You are in an ~N\times M~ grid. Each cell has a colour (colours are numbered from ~1~ to ~K~). You start at ~(1,1)~ and need to reach ~(N,M)~.

You can move up, down, left, or right, however, on each move, the colour of the new cell you move to must be different from the colour of your current cell.

Input Specification

The first line contains ~N,M,K~.

The next ~N~ lines each contain ~M~ integers, the colours of each cell in the grid.

Output Specification

Output the shortest number of moves to get from ~(1,1)~ to ~(N,M)~, or ~-1~ if impossible.

Constraints

~1\leq N,M\leq 10^3~

~1\leq K\leq 10^6~

Sample Input 1

3 4 5
3 1 4 2
5 2 1 3  
4 5 2 1

Output for Sample Input 1

5

Explanation of Output for Sample Input 1

One possible path is: ~(1,1)~, ~(1,2)~, ~(1,3)~, ~(1,4)~, ~(2,4)~, ~(3,4)~, which takes 5 moves.

Sample Input 2

3 3 2
1 2 2
2 2 2
2 1 1

Output for Sample Input 2

-1

Sample Input 3

2 4 4
1 1 4 1
2 3 3 3

Output for Sample Input 3

6