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 maxn = 51;
int res[maxn][maxn][maxn];
int a[2], b[2];
int cnt[2];
int perm[3];
int pdir[3];
int x[2][3];
inline void change(int man, int pos, int dch) {
  x[man][pos] += dch;
  assert(res[x[man][0]][x[man][1]][x[man][2]] == -1);
  res[x[man][0]][x[man][1]][x[man][2]] = a[man] + b[man] * cnt[man]++;
}
void makethis(int man, int w, int h) {
  if (w & 1) {
    for (int i = 0; i < h - 1; i++) change(man, perm[2], pdir[2]);
    for (int i = 0; i < w - 1; i++) change(man, perm[1], pdir[1]);
    for (int i = 0; i < h - 1; i++) {
      change(man, perm[2], -pdir[2]);
      for (int j = 0; j < w - 2; j++)
        change(man, perm[1], (i & 1) ? pdir[1] : -pdir[1]);
    }
  } else {
    for (int i = 0; i < w; i++) {
      for (int j = 0; j < h - 1; j++)
        change(man, perm[2], (i & 1) ? -pdir[2] : pdir[2]);
      if (i < w - 1) change(man, perm[1], pdir[1]);
    }
  }
}
int n0;
void printall() {
  for (int i = 0; i < n0; i++) {
    for (int j = n0 - 1; j >= 0; j--)
      for (int y = n0 - 1; y >= 0; y--) printf("%d%c", res[i][y][j], " \n"[!y]);
    printf("\n");
  }
  fflush(stdout);
}
int main() {
  while (scanf("%d", &n0) >= 1) {
    if (n0 == 1) {
      printf("1\n");
      continue;
    }
    cnt[0] = cnt[1] = 0;
    a[0] = 1, a[1] = (n0 + 1) * n0 * n0;
    b[0] = 1, b[1] = -1;
    x[0][0] = x[0][1] = 0;
    x[0][2] = x[1][0] = x[1][1] = x[1][2] = n0 - 1;
    x[1][!(n0 & 1)]++;
    memset(res, -1, sizeof(res));
    for (int j = 0; j < 2; j++)
      res[x[j][0]][x[j][1]][x[j][2]] = a[j] + b[j] * cnt[j]++;
    for (int n = n0; n >= 2; n--) {
      {
        perm[0] = !(n & 1), perm[1] = (n & 1), perm[2] = 2;
        pdir[1] = 1, pdir[2] = -1;
        makethis(0, n, n);
        change(0, !(n & 1), 1);
      }
      {
        perm[0] = !(n & 1), perm[1] = (n & 1), perm[2] = 2;
        pdir[1] = -1, pdir[2] = -1;
        makethis(1, n, n);
        change(1, !(n & 1), -1);
      }
      if (n == 2) break;
      {
        perm[0] = 2, perm[1] = (n & 1), perm[2] = !(n & 1);
        pdir[1] = 1, pdir[2] = 1;
        makethis(1, n, 1);
        change(1, 2, -1);
      }
      {
        perm[0] = 2, perm[1] = (n & 1), perm[2] = !(n & 1);
        pdir[1] = -1, pdir[2] = 1;
        makethis(0, n, n - 2);
        change(0, 2, -1);
      }
    }
    change(0, 2, -1);
    change(1, 2, -1);
    printall();
  }
  return 0;
}