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;
long long int cnt = 1;
long long int ans[55][55][55];
long long int n;
long long int x, y, z;
long long int dx[] = {0, 1, 0, 0, -1, 0};
long long int dy[] = {0, 0, -1, 0, 0, 1};
long long int dz[] = {-1, 0, 0, 1, 0, 0};
long long int tri(long long int n) { return n * n * n; }
void SET() {
  if (ans[x][y][z] != -1) return;
  ans[x][y][z] = cnt++;
}
pair<long long int, pair<long long int, long long int> > get(
    set<pair<long long int, pair<long long int, long long int> > > s,
    long long int sx, long long int sy, long long int sz) {
  pair<pair<long long int, long long int>,
       pair<long long int, pair<long long int, long long int> > >
      best;
  best = make_pair(make_pair(-1, -1), make_pair(-1, make_pair(-1, -1)));
  for (long long int dir = 0; dir < ((long long int)(6)); ++dir) {
    long long int xx = x + dx[dir];
    long long int yy = y + dy[dir];
    long long int zz = z + dz[dir];
    if (s.find(make_pair(xx, make_pair(yy, zz))) == s.end()) continue;
    long long int d0 = max(abs(sx - xx), max(sy - yy, sz - zz));
    long long int d1 = abs(sx - xx) + abs(sy - yy) + abs(sz - zz);
    best = max(best,
               make_pair(make_pair(d0, d1), make_pair(xx, make_pair(yy, zz))));
  }
  return best.second;
}
void getNext(long long int &x, long long int &y, long long int &z,
             long long int dir) {
  x += dx[dir];
  y += dy[dir];
  z += dz[dir];
}
int main() {
  memset(ans, -1, sizeof(ans));
  cin >> n;
  x = 0;
  y = n - 2;
  z = n - 2;
  if (n == 1) {
    cout << 1 << endl;
    return 0;
  }
  SET();
  for (long long int t = 0; t < n - 2; t++) {
    if (t % 2) {
      for (int turn = 0; t <= x; x--, turn++) {
        SET();
        if (turn % 2) {
          while (t <= --z) SET();
          z = t;
          while (++y <= n - 2) SET();
          y = n - 2;
        } else {
          while (t <= --y) SET();
          y = t;
          while (++z <= n - 2) SET();
          z = n - 2;
        }
      }
      x++;
      while (true) {
        pair<pair<long long int, long long int>,
             pair<long long int, pair<long long int, long long int> > >
            best;
        best = make_pair(make_pair(-1, -1), make_pair(-1, make_pair(-1, -1)));
        for (long long int dir = 0; dir < ((long long int)(6)); ++dir) {
          long long int xx = x + dx[dir];
          long long int yy = y + dy[dir];
          long long int zz = z + dz[dir];
          if (zz < t + 1 || n - 1 <= zz) continue;
          if (yy < t + 1 || n - 1 <= yy) continue;
          if (xx != x) continue;
          if (ans[xx][yy][zz] != -1) continue;
          long long int d0 = max(abs(x - xx), max((n - 1) - yy, (n - 1) - zz));
          long long int d1 =
              abs(x - xx) + abs((n - 1) - yy) + abs((n - 1) - zz);
          best = max(best, make_pair(make_pair(d0, d1),
                                     make_pair(xx, make_pair(yy, zz))));
        }
        if (best.first.first == -1) break;
        x = best.second.first;
        y = best.second.second.first;
        z = best.second.second.second;
        SET();
      }
    } else {
      for (int turn = 0; t <= z; z--, turn++) {
        SET();
        if (turn % 2) {
          while (t <= --x) SET();
          x = t;
          while (++y <= n - 2) SET();
          y = n - 2;
        } else {
          while (t <= --y) SET();
          y = t;
          while (++x <= n - 2) SET();
          x = n - 2;
        }
      }
      z++;
      while (true) {
        pair<pair<long long int, long long int>,
             pair<long long int, pair<long long int, long long int> > >
            best;
        best = make_pair(make_pair(-1, -1), make_pair(-1, make_pair(-1, -1)));
        for (long long int dir = 0; dir < ((long long int)(6)); ++dir) {
          long long int xx = x + dx[dir];
          long long int yy = y + dy[dir];
          long long int zz = z + dz[dir];
          if (xx < t + 1 || n - 1 <= xx) continue;
          if (yy < t + 1 || n - 1 <= yy) continue;
          if (zz != z) continue;
          if (ans[xx][yy][zz] != -1) continue;
          long long int d0 = max(abs((n - 1) - xx), max((n - 1) - yy, z - zz));
          long long int d1 =
              abs((n - 1) - xx) + abs((n - 1) - yy) + abs(z - zz);
          best = max(best, make_pair(make_pair(d0, d1),
                                     make_pair(xx, make_pair(yy, zz))));
        }
        if (best.first.first == -1) break;
        x = best.second.first;
        y = best.second.second.first;
        z = best.second.second.second;
        SET();
      }
    }
    if (t % 2)
      x++;
    else
      z++;
    SET();
  }
  x++;
  SET();
  y++;
  SET();
  z++;
  SET();
  y--;
  SET();
  x--;
  SET();
  y++;
  SET();
  long long int dir = 0;
  while (cnt <= tri(n)) {
    long long int next_dir = (dir + 1) % 6;
    {
      getNext(x, y, z, next_dir);
      if (0 <= x && x < n)
        if (0 <= y && y < n)
          if (0 <= z && z < n)
            if (x == n - 1 || y == n - 1 || z == n - 1)
              if (ans[x][y][z] == -1) dir = next_dir;
      getNext(x, y, z, (next_dir + 3) % 6);
    }
    getNext(x, y, z, dir);
    SET();
  }
  for (long long int i = 0; i < ((long long int)(n)); ++i) {
    for (long long int j = 0; j < ((long long int)(n)); ++j) {
      for (long long int k = 0; k < ((long long int)(n)); ++k)
        printf("%d ", (int)ans[i][j][k]);
      printf("\n");
    }
    printf("\n");
  }
}