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;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  return x * f;
}
const int MAXN = 100010;
const int INF = 1e9;
struct data {
  int x, y, z, id, mns;
} A, B;
int f[56][56][56], g[56][56][56];
inline void init(data A) {
  f[A.x][A.y][A.z] = A.id;
  return;
}
inline void Go(data &A, int n) {
  int dx = (A.x == 0 ? 1 : -1), dz = (A.z == 1 ? 1 : -1),
      dy = (A.y == 1 ? -1 : 1);
  A.y += dy;
  A.id += A.mns;
  for (int i = 1; i <= n + 1; i++) {
    for (int j = 1; j <= n + 1; j++) {
      init(A);
      if (j < n + 1) A.x += dx, A.id += A.mns;
    }
    if (i < n + 1) A.z += dz, A.id += A.mns, dx = -dx;
  }
  return;
}
int N, dx;
int main() {
  N = read();
  A.x = A.y = A.z = A.id = 1;
  A.mns = -1;
  B = A;
  B.mns = 1;
  for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= 4; j++) {
      init(B);
      if (j < 4) {
        if (B.x == 1 && B.y == 1)
          ++B.y;
        else if (B.x == 1 && B.y == 2)
          ++B.x;
        else if (B.x == 2 && B.y == 2)
          --B.y;
        else
          --B.x;
        B.id += 1;
      }
    }
    if (i < 3) B.z++, B.id += 1;
  }
  for (int n = 2; n < N; n++) {
    if (A.x == 1)
      dx = -1;
    else
      dx = 1;
    A.id--;
    A.x += dx;
    B.id++;
    B.x += dx;
    if (n & 1) {
      int dz = (A.z == 1 ? 1 : -1), dy;
      for (int j = 1; j <= n + 1; j++) {
        init(A);
        if (j < n + 1) A.z += dz, --A.id;
      }
      dy = (B.y == 1 ? 1 : -1);
      dz = (B.z == 1 ? 1 : -1);
      for (int j = 1; j <= n + 1; j++) {
        for (int k = 1; k < n; k++) {
          init(B);
          if (k < n - 1) B.y += dy, ++B.id;
        }
        if (j < n + 1) dy = -dy, B.z += dz, ++B.id;
      }
    } else {
      int dy = (A.y == 1 ? 1 : -1), dz;
      for (int j = 1; j <= n; j++) {
        init(A);
        if (j < n) A.y += dy, --A.id;
      }
      dy = (B.y == 1 ? 1 : -1);
      dz = (B.z == 1 ? 1 : -1);
      for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= n; k++) {
          init(B);
          if (k < n) B.z += dz, ++B.id;
        }
        if (j < n) dz = -dz, B.y += dy, ++B.id;
      }
    }
    Go(A, n);
    Go(B, n);
    if (dx == 1) dx = 0;
    for (int i = 1 + dx; i <= n + 1 + dx; i++) {
      for (int j = 0; j <= n + 1; j++) {
        for (int k = 1; k <= n + 1; k++) g[i - dx][j + 1][k] = f[i][j][k];
      }
    }
    for (int i = 1; i <= n + 1; i++) {
      for (int j = 1; j <= n + 2; j++)
        for (int k = 1; k <= n + 1; k++) f[i][k][j] = g[i][j][k];
    }
    A.x -= dx;
    A.y++;
    B.x -= dx;
    ++B.y;
    swap(A.y, A.z);
    swap(B.y, B.z);
  }
  int mn = INF;
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      for (int k = 1; k <= N; k++) mn = min(mn, f[i][j][k]);
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      for (int k = 1; k <= N; k++) printf("%d ", f[i][j][k] - mn + 1);
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}