Description

The cows have revised their game of leapcow. They now play in the middle of a huge pasture upon which they have marked a grid that bears a remarkable resemblance to a chessboard of N rows and N columns (3 <= N <= 365). 

Here's how they set up the board for the new leapcow game: 

* First, the cows obtain N x N squares of paper. They write the integers from 1 through N x N, one number on each piece of paper. 

* Second, the 'number cow' places the papers on the N x N squares in an order of her choosing. 

Each of the remaining cows then tries to maximize her score in the game. 

* First, she chooses a starting square and notes its number. 

* Then, she makes a 'knight' move (like the knight on a chess board) to a square with a higher number. If she's particularly strong, she leaps to the that square; otherwise she walks. 

* She continues to make 'knight' moves to higher numbered squares until no more moves are possible. 

Each square visited by the 'knight' earns the competitor a single point. The cow with the most points wins the game. 

Help the cows figure out the best possible way to play the game.

Input

* Line 1: A single integer: the size of the board 

* Lines 2.. ...: These lines contain space-separated integers that tell the contents of the chessboard. The first set of lines (starting at the second line of the input file) represents the first row on the chessboard; the next set of lines represents the next row, and so on. To keep the input lines of reasonable length, when N > 15, a row is broken into successive lines of 15 numbers and a potentially shorter line to finish up a row. Each new row begins on its own line. 

Output

* Line 1: A single integer that is the winning cow's score; call it W. 

* Lines 2..W+1: Output, one per line, the integers that are the starting square, the next square the winning cow visits, and so on through the last square. If a winning cow can choose more than one path, show the path that would be the 'smallest' if the paths were sorted by comparing their respective 'square numbers'. 

Sample Input

41 3 2 164 10 6 78 11 5 129 13 14 15

Sample Output

72459101213 题意：给你一个矩阵，问你按照象棋马的走法，下一步比上一步的数大，问长度最长的序列是多长，然后输出序列。如果有多个最长序列输出字典序最小的那个。 这是看到的一个代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
           
          
         
        
       
      

知识点：

这个代码的主要想法是，如同最短路一样，path中储存的是当前节点的下一步应该走的位置，然后进行搜索直到遍历了所有的点。