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;
using ll = long long int;
using pii = pair<int, int>;
int n;
int cube[57][57][57];
int thi, tlo;
void fillSideOdd(int s) {
  int x = s - 1;
  for (int z = s - 1; z >= 0; z--) {
    if (z & 1)
      for (int y = s - 1; y >= 1; y--) cube[x][y][z] = thi++;
    else
      for (int y = 1; y < s; y++) cube[x][y][z] = thi++;
  }
}
void fillTopOdd(int s) {
  for (int x = s - 1; x >= 0; x--) cube[x][s][0] = thi++;
  for (int x = (0); x < (s); ++x) {
    if (x & 1)
      for (int z = s - 1; z >= 1; z--) cube[x][s][z] = thi++;
    else
      for (int z = 1; z < s; z++) cube[x][s][z] = thi++;
  }
}
void fillBottomOdd(int s) {
  for (int x = 0; x < s; x++) cube[x][0][0] = tlo--;
  for (int x = s - 1; x >= 0; x--) {
    if (x & 1)
      for (int z = s - 1; z >= 1; z--) cube[x][0][z] = tlo--;
    else
      for (int z = 1; z < s; z++) cube[x][0][z] = tlo--;
  }
}
void rotate(int s) {
  for (int x = 0; x < (s - 1); ++x)
    for (int y = 0; y < ((s + 1) / 2); ++y)
      for (int z = 0; z < ((s) / 2); ++z) {
        int &a = cube[x][y][z];
        int &b = cube[x][s - 1 - z][y];
        int &c = cube[x][s - 1 - y][s - 1 - z];
        int &d = cube[x][z][s - 1 - y];
        int t = d;
        d = c, c = b, b = a, a = t;
      }
}
void fillSideEven(int s) {
  int x = s - 1;
  for (int y = 1; y < s; ++y) {
    if (y & 1)
      for (int z = s - 1; z >= 0; z--) cube[x][y][z] = thi++;
    else
      for (int z = 0; z < s; z++) cube[x][y][z] = thi++;
  }
}
void fillTopEven(int s) {
  for (int z = 0; z < s; z++)
    if (z & 1)
      for (int x = 0; x < s; x++) cube[x][s][z] = thi++;
    else
      for (int x = s - 1; x >= 0; x--) cube[x][s][z] = thi++;
}
void fillBottomEven(int s) {
  for (int z = 0; z < s; z++)
    if (z & 1)
      for (int x = s - 1; x >= 0; x--) cube[x][0][z] = tlo--;
    else
      for (int x = 0; x < s; x++) cube[x][0][z] = tlo--;
}
void adjust(int n) {
  int m = 1;
  for (int x = 0; x < (n); ++x)
    for (int y = 0; y < (n + 1); ++y)
      for (int z = 0; z < (n); ++z) m = min(m, cube[x][y][z]);
  for (int x = 0; x < (n); ++x)
    for (int y = 0; y < (n + 1); ++y)
      for (int z = 0; z < (n); ++z) cube[x][y][z] += -m + 1;
}
void print(int n) {
  for (int z = 0; z < (n); ++z) {
    for (int y = n - 1; y >= 0; y--) {
      for (int x = 0; x < (n); ++x) cout << cube[x][y][z] << ' ';
      cout << endl;
    }
    cout << endl;
  }
}
int main() {
  cin >> n;
  if (n < 3) {
    if (n == 1)
      cout << 1 << endl;
    else {
      cout << "2 3" << endl << "1 4" << endl;
      cout << endl;
      cout << "7 6" << endl << "8 5" << endl;
    }
    return 0;
  }
  cube[0][1][0] = 1;
  cube[0][2][0] = 2;
  cube[1][2][0] = 3;
  cube[1][1][0] = 4;
  cube[1][1][1] = 5;
  cube[1][2][1] = 6;
  cube[0][2][1] = 7;
  cube[0][1][1] = 8;
  cube[0][1][2] = 9;
  cube[0][2][2] = 10;
  cube[1][2][2] = 11;
  cube[1][1][2] = 12;
  thi = 13;
  tlo = 0;
  for (int z = 3; z < n; ++z) {
    if (z & 1)
      fillSideOdd(z), fillTopOdd(z), fillBottomOdd(z);
    else
      fillSideEven(z), fillTopEven(z), fillBottomEven(z);
    rotate(z + 1);
  }
  if (!(n & 1))
    fillSideEven(n), fillBottomEven(n);
  else
    fillSideOdd(n), fillBottomOdd(n);
  adjust(n);
  print(n);
  return 0;
}