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 point {
  int x, y, z;
  bool operator<(const point &b) const {
    return tie(x, y, z) < tie(b.x, b.y, b.z);
  }
  point operator+(const point &b) { return {x + b.x, y + b.y, z + b.z}; }
  point operator*(int l) { return {x * l, y * l, z * l}; }
  point operator-() { return {-x, -y, -z}; }
};
map<point, int> a;
int id = 0;
void constrSquare(point o, point x, point y, int n) {
  auto a_at = [&](int i, int j) -> int & { return a[o + x * i + y * j]; };
  if (n % 2 == 0) {
    for (int j = 0; j < n; ++j)
      if (j % 2 == 0) {
        for (int i = 0; i < n; ++i) a_at(i, j) = ++id;
      } else {
        for (int i = n - 1; i >= 0; --i) a_at(i, j) = ++id;
      }
  } else {
    for (int i = 0; i < n; ++i)
      if (i % 2 == 0) {
        for (int j = 0; j < n - 1; ++j) a_at(i, j) = ++id;
      } else {
        for (int j = n - 2; j >= 0; --j) a_at(i, j) = ++id;
      }
    for (int i = n - 1; i >= 0; --i) a_at(i, n - 1) = ++id;
  }
}
void constrCube(point o, point x, point y, point z, int n) {
  auto at = [&](int i, int j, int k) { return o + x * i + y * j + z * k; };
  constrSquare(o, x, y, n);
  if (n > 1) {
    for (int i = 1; i < n; ++i) a[at(0, n - 1, i)] = ++id;
    constrCube(at(1, n - 1, n - 1), x, -z, -y, n - 1);
    constrSquare(at(0, 0, 1), y, z, n - 1);
  }
  constrSquare(at(0, 0, n), x, y, n);
}
void EXEC() {
  int n;
  cin >> n;
  constrCube({0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 0, 1}, n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      for (int k = 0; k < n; ++k) printf("%d ", a[{i, j, k}]);
      printf("\n");
    }
    printf("\n");
  }
}
int main() {
  EXEC();
  return 0;
}