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;
int a[100][100][100];
int xl, xr, yl, yr, zl, zr, n;
int up = 0, down = 1;
int revv = 0;
int posx, posy, posz;
inline int nxtp() {
  if (up >= 2) return ++up;
  return --up;
}
inline int nxtd() {
  if (down >= 2) return ++down;
  return --down;
}
inline bool cmp(pair<int, int> a, pair<int, int> b) {
  return a.second < b.second;
}
int main() {
  scanf("%d", &n);
  xl = 50, xr = 50;
  yl = 50, yr = 51;
  zl = 50, zr = 51;
  a[50][50][51] = ++up;
  a[50][50][50] = ++up;
  a[50][51][50] = ++up;
  a[50][51][51] = ++up;
  for (int i = 2; i <= n; i++) {
    if (revv == 0) {
      xr++;
      int x = xr;
      int rev = 0;
      for (int y = yr; y >= yl; y--) {
        if (rev == 0)
          for (int z = zr; z >= zl; z--) a[x][y][z] = nxtp();
        else
          for (int z = zl; z <= zr; z++) a[x][y][z] = nxtp();
        rev ^= 1;
      }
      xl--;
      x = xl;
      rev = 0;
      for (int y = yl; y <= yr; y++) {
        if (rev == 0)
          for (int z = zr; z >= zl; z--) a[x][y][z] = nxtd();
        else
          for (int z = zl; z <= zr; z++) a[x][y][z] = nxtd();
        rev ^= 1;
      }
      zr++;
      int z = zr;
      x = xr;
      for (int y = yl; y <= yr; y++) a[x][y][z] = nxtp();
      if ((yr - yl + 1) % 2 == 0) {
        rev = 0;
        for (int y = yr; y >= yl; y--) {
          if (rev == 0)
            for (int x = xl; x <= xr - 1; x++) a[x][y][z] = nxtd();
          else
            for (int x = xr - 1; x >= xl; x--) a[x][y][z] = nxtd();
          rev ^= 1;
        }
      } else {
        rev = 0;
        for (int x = xr - 1; x >= xl; x--) {
          if (rev == 0)
            for (int y = yr; y >= yl + 1; y--) a[x][y][z] = nxtd();
          else
            for (int y = yl; y <= yr - 1; y++) a[x][y][z] = nxtd();
          rev ^= 1;
        }
        int y = yl;
        for (int x = xr - 1; x >= xl; x--) a[x][y][z] = nxtd();
      }
      revv ^= 1;
    } else {
      yr++;
      int rev = 0, y = yr, x = xr;
      for (int z = zr; z >= zl; z--) a[x][y][z] = nxtp();
      rev = 0;
      for (int z = zl; z <= zr; z++) {
        if (rev == 0)
          for (int x = xr - 1; x >= xl; x--) a[x][y][z] = nxtp();
        else
          for (int x = xl; x <= xr - 1; x++) a[x][y][z] = nxtp();
        rev ^= 1;
      }
      yl--;
      y = yl;
      x = xl;
      for (int z = zr; z >= zl; z--) a[x][y][z] = nxtd();
      rev = 0;
      for (int z = zl; z <= zr; z++) {
        if (rev == 0)
          for (int x = xl + 1; x <= xr; x++) a[x][y][z] = nxtd();
        else
          for (int x = xr; x >= xl + 1; x--) a[x][y][z] = nxtd();
        rev ^= 1;
      }
      zr++;
      int z = zr;
      y = yl;
      for (int x = xr; x >= xl; x--) a[x][y][z] = nxtd();
      if ((xr - xl + 1) % 2 == 0) {
        rev = 0;
        for (int x = xl; x <= xr; x++) {
          if (rev == 0)
            for (int y = yr; y >= yl + 1; y--) a[x][y][z] = nxtp();
          else
            for (int y = yl + 1; y <= yr; y++) a[x][y][z] = nxtp();
          rev ^= 1;
        }
      } else {
        rev = 0;
        for (int y = yr; y >= yl + 1; y--) {
          if (rev == 0)
            for (int x = xl; x <= xr - 1; x++) a[x][y][z] = nxtp();
          else
            for (int x = xr - 1; x >= xl; x--) a[x][y][z] = nxtp();
          rev ^= 1;
        }
        x = xr;
        for (int y = yl + 1; y <= yr; y++) a[x][y][z] = nxtp();
      }
      revv ^= 1;
    }
  }
  if ((yr - yl + 1) != n) {
    int m = 1e9;
    for (int x = xl; x <= xr; x++)
      for (int y = yl + 1; y <= yr; y++)
        for (int z = zl; z <= zr - 1; z++) m = min(m, a[x][y][z]);
    for (int x = xl; x <= xr; x++) {
      for (int y = yl + 1; y <= yr; y++) {
        for (int z = zl; z <= zr - 1; z++) printf("%d ", a[x][y][z] - m + 1);
        puts("");
      }
      puts("");
    }
  } else {
    int m = 1e9;
    for (int x = xl + 1; x <= xr; x++)
      for (int y = yl; y <= yr; y++)
        for (int z = zl; z <= zr - 1; z++) m = min(m, a[x][y][z]);
    for (int x = xl + 1; x <= xr; x++) {
      for (int y = yl; y <= yr; y++) {
        for (int z = zl; z <= zr - 1; z++) printf("%d ", a[x][y][z] - m + 1);
        puts("");
      }
      puts("");
    }
  }
}