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;
int cur;
int a[55][55][55];
void yz_xy_xz(int n) {
  assert(a[n - 1][0][0] == cur);
  int x = n;
  int y, z;
  for (z = 0; z <= n; z++) {
    if (z & 1) {
      for (y = n - 1; y >= 0; y--) {
        a[x][y][z] = ++cur;
      }
    } else {
      for (y = 0; y < n; y++) {
        a[x][y][z] = ++cur;
      }
    }
  }
  z = n;
  for (x = n - 1; x >= 0; x--) {
    if (y == -1) {
      for (y = 0; y < n; y++) {
        a[x][y][z] = ++cur;
      }
    } else {
      for (y = n - 1; y >= 0; y--) {
        a[x][y][z] = ++cur;
      }
    }
  }
  assert(a[0][n - 1][n] == cur);
  y = n;
  if (n & 1) {
    for (int z = n; z >= 0; z--) {
      if (z & 1) {
        for (int x = 0; x < int(n + 1); x++) {
          a[x][y][z] = ++cur;
        }
      } else {
        for (int x = n; x >= 0; x--) {
          a[x][y][z] = ++cur;
        }
      }
    }
  } else {
    for (int x = 0; x < int(n + 1); x++) {
      if (x & 1) {
        for (int z = 1; z <= int(n); z++) {
          a[x][y][z] = ++cur;
        }
      } else {
        for (int z = n; z >= 1; z--) {
          a[x][y][z] = ++cur;
        }
      }
    }
    for (int x = n; x >= 0; x--) {
      a[x][y][0] = ++cur;
    }
  }
}
void reverse_cube(int n) {
  int N = n * n * n;
  for (int i = 0; i < int(n); i++) {
    for (int j = 0; j < int(n); j++) {
      for (int k = 0; k < int(n); k++) {
        a[i][j][k] = N + 1 - a[i][j][k];
      }
    }
  }
}
int b[55][55];
void rotate_cube(int n) {
  for (int z = 0; z < int(n); z++) {
    for (int x = 0; x < int(n); x++) {
      for (int y = 0; y < int(n); y++) {
        b[n - y - 1][x] = a[x][y][z];
      }
    }
    for (int x = 0; x < int(n); x++) {
      for (int y = 0; y < int(n); y++) {
        a[x][y][z] = b[x][y];
      }
    }
  }
}
void out(int n) {
  for (int i = 0; i < int(n); i++) {
    if (i) printf("\n");
    for (int j = 0; j < int(n); j++) {
      for (int k = 0; k < int(n); k++) {
        if (k) printf(" ");
        printf("%d", a[i][j][k]);
      }
      printf("\n");
    }
  }
}
int main() {
  int n;
  cin >> n;
  cur = 1;
  a[0][0][0] = 1;
  for (int i = 1; i <= int(n - 1); i++) {
    yz_xy_xz(i);
    reverse_cube(i + 1);
    rotate_cube(i + 1);
  }
  out(n);
  return 0;
}