Problem: You've got an n × n × n cube, split into unit cubes. Your task is to number all unit cubes in this cube with positive integers from 1 to n3 so that: 

  * each number was used as a cube's number exactly once; 
  * for each 1 ≤ i < n3, unit cubes with numbers i and i + 1 were neighbouring (that is, shared a side); 
  * for each 1 ≤ i < n there were at least two different subcubes with sizes i × i × i, made from unit cubes, which are numbered with consecutive numbers. That is, there are such two numbers x and y, that the unit cubes of the first subcube are numbered by numbers x, x + 1, ..., x + i3 - 1, and the unit cubes of the second subcube are numbered by numbers y, y + 1, ..., y + i3 - 1. 



Find and print the required numeration of unit cubes of the cube.

Input

The first line contains a single integer n (1 ≤ n ≤ 50) — the size of the cube, whose unit cubes need to be numbered.

Output

Print all layers of the cube as n n × n matrices. Separate them with new lines. Print the layers in the order in which they follow in the cube. See the samples for clarifications. 

It is guaranteed that there always is a solution that meets the conditions given in the problem statement.

Examples

Input

3


Output

1 4 17 
2 3 18 
27 26 19 

8 5 16 
7 6 15 
24 25 20 

9 12 13 
10 11 14 
23 22 21 

Note

In the sample the cubes with sizes 2 × 2 × 2 are numbered with integers 1, ..., 8 and 5, ..., 12.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
struct w {
  int x, y, z;
};
struct ww {
  int a, b, c, A, B, C, x, y, z;
};
int i, j, k, n, m, T, te;
int a[60][60][60];
inline void print() {
  int i, j, k;
  for (k = 1; k <= n; k++) {
    for (j = 1; j <= n; j++) {
      for (i = 1; i <= n; i++) printf("%d ", a[i][j][k]);
      printf("\n");
    }
    printf("\n");
  }
}
inline void get(w A, ww B, int t) {
  int b[3] = {A.x, A.y, A.z};
  a[b[B.a]][b[B.b]][b[B.c]] = t;
}
inline void work1(int n, int l, int r, ww A);
inline void work2(int n, int l, int r, ww A) {
  w B = {A.x, A.y, A.z};
  int i, j;
  if (n & 1) {
    int vx = A.A, vz = A.C;
    for (i = 1; i <= n; i++) {
      for (j = 1; j <= n - 1; j++) {
        get(B, A, l);
        l++;
        if (i == n && j == n - 1) break;
        if (j == n - 1)
          B.x += vx, vz *= -1;
        else
          B.z += vz;
      }
    }
    B.y += A.B;
  } else {
    int vx = A.A, vz = A.C;
    for (i = 1; i <= n - 1; i++) {
      for (j = 1; j <= n; j++) {
        get(B, A, l);
        l++;
        if (i == n - 1 && j == n) break;
        if (j == n)
          B.z += vz, vx *= -1;
        else
          B.x += vx;
      }
    }
    B.y += A.B;
  }
  work1(n, l, r, (ww){A.c, A.b, A.a, -A.C, A.B, -A.A, B.z, B.y, B.x});
}
inline void work1(int n, int l, int r, ww A) {
  w B = {A.x, A.y, A.z};
  if (n == 2) {
    get(B, A, l);
    B.z += A.C;
    get(B, A, l + 1);
    return;
  }
  int i, j;
  w C = {A.x, A.y + A.B * (n - 2), A.z + A.C * (n - 1)};
  int vx = A.A, vy = A.B;
  for (i = 1; i <= n - 1; i++) {
    for (j = 1; j <= n - 1; j++) {
      get(B, A, l);
      get(C, A, r);
      l++, r--;
      if (i == n - 1 && j == n - 1) break;
      if (j < n - 1)
        B.x += vx, C.x += vx;
      else
        B.y += vy, C.y -= vy, vx *= -1;
    }
  }
  B.z += A.C, C.z -= A.C;
  work2(n - 1, l, r,
        (ww){A.a, A.b, A.c, A.A * ((n - 1) & 1 ? -1 : 1), -A.B, A.C, B.x, B.y,
             B.z});
}
int main() {
  scanf("%d", &n);
  if (n == 1) {
    printf("1\n");
    return 0;
  }
  int A = n * (2 * n - 1);
  work1(n, A + 1, n * n * n, (ww){0, 1, 2, 1, 1, 1, 1, 2, 1});
  {
    w B = {1, 1, 1};
    ww C = {0, 1, 2};
    for (i = 1; i <= n; i++) {
      for (j = 1; j <= 2 * n - 1; j++) {
        get(B, C, A);
        A--;
        if (j == 2 * n - 1) break;
        if (i & 1) {
          if (j < n)
            B.x++;
          else
            B.y++;
        } else {
          if (j < n)
            B.y--;
          else
            B.x--;
        }
      }
      B.z++;
    }
  }
  print();
  return 0;
}