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;
const int N = 55;
int gi() {
  int x = 0, o = 1;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
  if (ch == '-') o = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  return x * o;
}
vector<pair<int, int> > ha_path(int n, int m) {
  vector<pair<int, int> > ret;
  if (m & 1) {
    int x = 1, y = 1;
    while (1) {
      ret.push_back(make_pair(x, y));
      if (x == 1 && y == m) break;
      if (y == 1) {
        if (x & 1)
          ++y;
        else
          ++x;
      } else if (y == 2) {
        if (x == n)
          ++y;
        else if (x & 1)
          ++x;
        else
          --y;
      } else {
        if (x < n && !(y & 1))
          ++x;
        else if (x > 1 && (y & 1))
          --x;
        else
          ++y;
      }
    }
  } else {
    int x = 1, y = 1;
    while (1) {
      ret.push_back(make_pair(x, y));
      if (x == 1 && y == m) break;
      if (x < n && (y & 1))
        ++x;
      else if (x > 1 && !(y & 1))
        --x;
      else
        ++y;
    }
  }
  return ret;
}
int n, a[N][N][N], b[N][N][N];
void rev(int n) {
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      for (int k = 1; k <= n + 1; k++) a[i][k][j] = b[i][j][k];
}
void print(int n) {
  for (int i = 1; i <= n; i++, cout << '\n')
    for (int j = 1; j <= n; j++, cout << '\n')
      for (int k = 1; k <= n + 1; k++) cout << b[i][j][k] << ' ';
}
int main() {
  cin >> n;
  if (n == 1) return cout << 1, 0;
  a[1][1][1] = 1;
  a[1][2][1] = 8;
  a[1][3][1] = 9;
  a[2][1][1] = 4;
  a[2][2][1] = 5;
  a[2][3][1] = 10;
  a[1][1][2] = 2;
  a[1][2][2] = 7;
  a[1][3][2] = 12;
  a[2][1][2] = 3;
  a[2][2][2] = 6;
  a[2][3][2] = 11;
  for (int t = 2; t < n; t++) {
    vector<pair<int, int> > p = ha_path(t + 1, t + 1);
    int s = 1;
    for (auto x : p) b[x.first][x.second][1] = s++;
    for (int i = t + 1; i; i--) b[1][i][2] = s++;
    int pre = s;
    for (int i = 1; i <= t; i++)
      for (int j = 1; j <= t + 1; j++)
        for (int k = 1; k <= t; k++)
          b[i + 1][j][k + 1] = a[i][j][k] + pre - 1, ++s;
    p = ha_path(t - 1, t + 1);
    for (auto x : p) b[1][t + 1 - x.second + 1][t + 1 - x.first + 1] = s++;
    p = ha_path(t + 1, t + 1);
    for (auto x : p) b[x.first][x.second][t + 2] = s++;
    if (t < n - 1)
      rev(t + 1);
    else
      memcpy(a, b, sizeof(a));
  }
  for (int i = 1; i <= n; i++, cout << '\n')
    for (int j = 1; j <= n; j++, cout << '\n')
      for (int k = 1; k <= n; k++) cout << a[i][j][k] << ' ';
  return 0;
}