C. Labs

C. Labs

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

In order to do some research, n2n2 labs are built on different heights of a mountain. Let's enumerate them with integers from 11 to n2n2, such that the lab with the number 11 is at the lowest place, the lab with the number 22 is at the second-lowest place, ……, the lab with the number n2n2 is at the highest place.

To transport water between the labs, pipes are built between every pair of labs. A pipe can transport at most one unit of water at a time from the lab with the number uu to the lab with the number vv if u>vu>v.

Now the labs need to be divided into nn groups, each group should contain exactly nn labs. The labs from different groups can transport water to each other. The sum of units of water that can be sent from a group AA to a group BB is equal to the number of pairs of labs (u,vu,v) such that the lab with the number uu is from the group AA, the lab with the number vv is from the group BB and u>vu>v. Let's denote this value as f(A,B)f(A,B) (i.e. f(A,B)f(A,B) is the sum of units of water that can be sent from a group AA to a group BB).

For example, if n=3n=3 and there are 33 groups XX, YY and ZZ: X={1,5,6},Y={2,4,9}X={1,5,6},Y={2,4,9} and Z={3,7,8}Z={3,7,8}. In this case, the values of ff are equal to:

• f(X,Y)=4f(X,Y)=4 because of 5→25→2, 5→45→4, 6→26→2, 6→46→4,
• f(X,Z)=2f(X,Z)=2 because of 5→35→3, 6→36→3,
• f(Y,X)=5f(Y,X)=5 because of 2→12→1, 4→14→1, 9→19→1, 9→59→5, 9→69→6,
• f(Y,Z)=4f(Y,Z)=4 because of 4→34→3, 9→39→3, 9→79→7, 9→89→8,
• f(Z,X)=7f(Z,X)=7 because of 3→13→1, 7→17→1, 7→57→5, 7→67→6, 8→18→1, 8→58→5, 8→68→6,
• f(Z,Y)=5f(Z,Y)=5 because of 3→23→2, 7→27→2, 7→47→4, 8→28→2, 8→48→4.

Please, divide labs into nn groups with size nn, such that the value minf(A,B)minf(A,B) over all possible pairs of groups AA and BB (A≠BA≠B) is maximal.

In other words, divide labs into nn groups with size nn, such that minimum number of the sum of units of water that can be transported from a group AA to a group BB for every pair of different groups AA and BB (A≠BA≠B) as big as possible.

Note, that the example above doesn't demonstrate an optimal division, but it demonstrates how to calculate the values ff for some division.

If there are many optimal divisions, you can find any.

Input

The only line contains one number nn (2≤n≤3002≤n≤300).

Output

Output nn lines:

In the ii-th line print nn numbers, the numbers of labs of the ii-th group, in any order you want.

If there are multiple answers, that maximize the minimum number of the sum of units of water that can be transported from one group the another, you can print any.

Example

input

Copy

3

output

Copy

2 8 5
9 3 4
7 6 1

Note

In the first test we can divide 99 labs into groups {2,8,5},{9,3,4},{7,6,1}{2,8,5},{9,3,4},{7,6,1}.

From the first group to the second group we can transport 44 units of water (8→3,8→4,5→3,5→48→3,8→4,5→3,5→4).

From the first group to the third group we can transport 55 units of water (2→1,8→7,8→6,8→1,5→12→1,8→7,8→6,8→1,5→1).

From the second group to the first group we can transport 55 units of water (9→2,9→8,9→5,3→2,4→29→2,9→8,9→5,3→2,4→2).

From the second group to the third group we can transport 55 units of water (9→7,9→6,9→1,3→1,4→19→7,9→6,9→1,3→1,4→1).

From the third group to the first group we can transport 44 units of water (7→2,7→5,6→2,6→57→2,7→5,6→2,6→5).

From the third group to the second group we can transport 44 units of water (7→3,7→4,6→3,6→47→3,7→4,6→3,6→4).

The minimal number of the sum of units of water, that can be transported from one group to another is equal to 44. It can be proved, that it is impossible to make a better division.

=========================================================================

最小值最大的套路就是平均，考虑将每组都分到大小关系差不多的数，那么以n=3为例就是

1 2 3组分别分到

9 8 7  都是最大的三个

然后接着分654

,值得注意的是，为了更平均，把这些倒着来一遍

4 5 6 

然后是

3 2 1

# include 
#include
# include
# include
# include
using namespace std;
typedef long long int ll;
 
int ans[500][500];
int main()
{
   int n;
 
   cin>>n;
 
   int left=n*(n-1)+1;
   int right=n*n;
 
 
   for(int i=1;i<=n;i++)
   {
 
       if(i%2)
       {
           for(int j=1;j<=n;j++)
           {
               ans[j][i]=right;
               right--;
           }
       }
       else
       {
           for(int j=n;j>=1;j--)
           {
               ans[j][i]=right;
 
               right--;
           }
 
       }
 
 
 
 
   }
 
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=n;j++)
       {
           cout<" ";
       }
 
       cout<
   }
 
    return  0;
}