468. A bit of classic

Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Everybody loves classical problems! Real professional can solve them quickly and gaily come to more difficult problems, and amateurs are just able to solve them, which is also important for popularization of computer programming contests. Here you are required to solve classical problem not only in chess but in computer science as well. Given integer N, find a way to bypass every cell of a chessboard N x N exactly once with a chess knight.

Input
Input file contains integer number N — size of the board (1 ≤ N ≤ 250).

Output
If there is no solution for the given size of the board, write to the output file the only message
No solution.
(without quotes). Otherwise, write to the first line of the output file message
There is solution:
, and then to every of the N following lines write N numbers separated by spaces — order of traversal of the board. Each of the numbers from 1 to N2 should occur in this sequence exactly once. Knight may start and end its trip at any cell of the chessboard.

Example(s)
sample input
sample output
3
No solution.

sample input
sample output
5
There is solution:
 1 14 9 20 3
 24 19 2 15 10
 13 8 25 4 21
 18 23 6 11 16
 7 12 17 22 5




Online Contester Team © 2002 - 2010. All rights reserved.