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 = 100 + 10;
int rd() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch ^ 48);
    ch = getchar();
  }
  return x * w;
}
int id[N][N][N], vs[N][N][N];
int n, sx, sy, sz, tx, ty, tz, ls;
void mv(int dx, int dy, int dz, int dt) {
  sx += dx, sy += dy, sz += dz;
  id[sx][sy][sz] = ls + dt, ls = id[sx][sy][sz];
}
int main() {
  n = rd();
  if (n == 1) {
    puts("1");
    return 0;
  }
  sx = sy = tx = ty = 50, sz = tz = 1, vs[sx][sy][sz] = 1;
  ls = id[sx][sy][sz], mv(0, 1, 0, 1);
  int px = 1;
  for (int s = 2; s <= n; ++s) {
    if (s & 1) {
      ls = id[sx][sy][sz];
      mv(0, 0, 1, px);
      for (int i = 2; i <= s; ++i) mv(-1, 0, 0, px);
      swap(sx, tx), swap(sy, ty), swap(sz, tz), ls = id[sx][sy][sz], px = -px;
      mv(0, 0, 1, px);
      for (int j = 2; j <= s - 2; ++j) mv(0, -1, 0, px);
      for (int i = 2; i <= s; ++i) mv(1, 0, 0, px);
      for (int j = s - 3; j > 0; --j) {
        mv(0, 1, 0, px);
        for (int i = 2; i <= s - 1; ++i) mv((j & 1) ? 1 : -1, 0, 0, px);
      }
      mv(0, 1, 0, px);
      for (int j = 2; j <= s; ++j) mv(0, 0, -1, px);
      for (int i = 2; i <= s; ++i) mv(-1, 0, 0, px);
      for (int i = 2; i <= s; ++i) {
        mv(0, 0, 1, px);
        for (int j = 2; j < s; ++j) mv((i & 1) ? -1 : 1, 0, 0, px);
      }
      swap(sx, tx), swap(sy, ty), swap(sz, tz), ls = id[sx][sy][sz], px = -px;
      mv(0, -1, 0, px);
      for (int j = 2; j <= s; ++j) mv(0, 0, -1, px);
      for (int i = 2; i <= s; ++i) mv(1, 0, 0, px);
      for (int i = 2; i <= s; ++i) {
        mv(0, 0, 1, px);
        for (int j = 2; j < s; ++j) mv((i & 1) ? 1 : -1, 0, 0, px);
      }
    } else {
      ls = id[sx][sy][sz];
      mv(0, 0, 1, px);
      if (s > 2)
        for (int i = 2; i <= s; ++i) mv(0, 1, 0, px);
      swap(sx, tx), swap(sy, ty), swap(sz, tz), ls = id[sx][sy][sz], px = -px;
      mv(0, 0, 1, px);
      if (s > 2)
        for (int i = 1; i <= s; ++i) {
          for (int j = 2; j <= s - 2; ++j) mv((i & 1) ? 1 : -1, 0, 0, px);
          if (i < s) mv(0, -1, 0, px);
        }
      mv(-1, 0, 0, px);
      for (int i = 1; i <= s; ++i) {
        for (int j = 2; j <= s; ++j) mv(0, 0, (i & 1) ? -1 : 1, px);
        if (i < s) mv(0, 1, 0, px);
      }
      swap(sx, tx), swap(sy, ty), swap(sz, tz), ls = id[sx][sy][sz], px = -px;
      mv(1, 0, 0, px);
      for (int i = 1; i <= s; ++i) {
        for (int j = 2; j <= s; ++j) mv(0, 0, (i & 1) ? -1 : 1, px);
        if (i < s) mv(0, -1, 0, px);
      }
    }
  }
  if (n & 1) {
    int mi = n * n * n;
    for (int i = tx; i <= sx; ++i)
      for (int j = sy; j < ty; ++j)
        for (int k = sz; k; --k) mi = min(mi, id[i][j][k] - 1);
    for (int k = sz; k; --k) {
      for (int i = tx; i <= sx; ++i) {
        for (int j = sy; j < ty; ++j) printf("%d ", id[i][j][k] - mi);
        puts("");
      }
      puts("");
    }
  } else {
    int mi = n * n * n;
    for (int i = tx; i < sx; ++i)
      for (int j = sy; j <= ty; ++j)
        for (int k = sz; k; --k) mi = min(mi, id[i][j][k] - 1);
    for (int k = sz; k; --k) {
      for (int i = tx; i < sx; ++i) {
        for (int j = sy; j <= ty; ++j) printf("%d ", id[i][j][k] - mi);
        puts("");
      }
      puts("");
    }
  }
  return 0;
}