PLCNUM1 - Place the Numbers I

Little Chucha is having a lot of fun with her new computer game. She is given a NxN board which she has to fill with the numbers 1 to N^2, no repetitions allowed. The computer calculates the sum of distances for each pair of consecutive numbers, that is, 1 -> 2, 2 -> 3, ..., N^2 -> 1. The goal is to make that sum as short as possible.

Input

Input consists of a single integer number 1<=N<=100, the size of the board.

Output

Output one possible placing of the numbers. You are to write N lines, N space separated integers each.

Example

Input:
3

Output:
1 2 3
4 5 6
7 8 9

Score:
Score for the example is:
Distance 1 -> 2 : 1
Distance 2 -> 3 : 1
Distance 3 -> 4 : 3
Distance 4 -> 5 : 1
Distance 5 -> 6 : 1
Distance 6 -> 7 : 3
Distance 7 -> 8 : 1
Distance 8 -> 9 : 1
Distance 9 -> 1 : 4
Sum of distances (SOD): 16, Min SOD: 10, Score: 1+16-10=7 points.

Added by:Yandry Perez
Date:2009-04-22
Time limit:0.600s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET

hide comments
2017-09-27 09:23:38 [Rampage] Blue.Mary
The judge of this problem is broken.
[Edit] Now the judge of this problem works well.

Last edit: 2022-08-06 05:50:32
2011-01-24 09:53:10 rockdude
is ter any algorithm to solve this prob?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.