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;
typedef int cube[N][N][N];
cube M[N];
void viewLayer(cube X, int n, int x, int y, int z) {
  if (x != -1)
    for (int y = 1; y <= n; ++y)
      for (int z = 1; z <= n; ++z) printf("%d%c", X[x][y][z], " \n"[z == n]);
  if (y != -1)
    for (int x = 1; x <= n; ++x)
      for (int z = 1; z <= n; ++z) printf("%d%c", X[x][y][z], " \n"[z == n]);
  if (z != -1)
    for (int x = 1; x <= n; ++x)
      for (int y = 1; y <= n; ++y) printf("%d%c", X[x][y][z], " \n"[y == n]);
}
void expandEven(int n, cube S, cube T) {
  int cp = 0;
  memcpy(T, S, sizeof(cube));
  for (int y = 1; y <= n; ++y)
    if (y & 1)
      for (int x = 1; x <= n; ++x) T[x][y][0] = cp--;
    else
      for (int x = n; x >= 1; --x) T[x][y][0] = cp--;
  cp = n * n * n + 1;
  for (int x = 1; x <= n; ++x)
    if (x & 1)
      for (int z = n; z >= 0; --z) T[x][0][z] = cp++;
    else
      for (int z = 0; z <= n; ++z) T[x][0][z] = cp++;
  for (int y = 0; y <= n; ++y)
    if (!(y & 1))
      for (int z = n; z >= 0; --z) T[n + 1][y][z] = cp++;
    else
      for (int z = 0; z <= n; ++z) T[n + 1][y][z] = cp++;
  static cube Q;
  for (int x = 1; x <= n + 1; ++x)
    for (int y = 0; y <= n; ++y)
      for (int z = 0; z <= n; ++z) Q[n + 1 - y][z + 1][x] = T[x][y][z];
  int delta = (n + 1) * (n + 1) * (n + 1) - --cp;
  for (int x = 1; x <= n + 1; ++x)
    for (int y = 1; y <= n + 1; ++y)
      for (int z = 1; z <= n + 1; ++z) Q[x][y][z] += delta;
  memcpy(T, Q, sizeof(cube));
}
void expandOdd(int n, cube S, cube T) {
  int cp = 0;
  memcpy(T, S, sizeof(cube));
  for (int y = 1; y <= n - 2; ++y)
    if (y & 1)
      for (int x = 1; x <= n; ++x) T[x][y][0] = cp--;
    else
      for (int x = n; x >= 1; --x) T[x][y][0] = cp--;
  for (int x = n; x >= 1; --x)
    if (x & 1)
      T[x][n - 1][0] = cp--, T[x][n][0] = cp--;
    else
      T[x][n][0] = cp--, T[x][n - 1][0] = cp--;
  cp = n * n * n + 1;
  for (int x = 1; x <= n; ++x)
    if (x & 1)
      for (int z = n; z >= 0; --z) T[x][0][z] = cp++;
    else
      for (int z = 0; z <= n; ++z) T[x][0][z] = cp++;
  for (int y = 0; y <= n; ++y)
    if (!(y & 1))
      for (int z = 0; z <= n; ++z) T[n + 1][y][z] = cp++;
    else
      for (int z = n; z >= 0; --z) T[n + 1][y][z] = cp++;
  static cube Q;
  for (int x = 1; x <= n + 1; ++x)
    for (int y = 0; y <= n; ++y)
      for (int z = 0; z <= n; ++z) Q[n + 1 - y][z + 1][x] = T[x][y][z];
  int delta = (n + 1) * (n + 1) * (n + 1) - --cp;
  for (int x = 1; x <= n + 1; ++x)
    for (int y = 1; y <= n + 1; ++y)
      for (int z = 1; z <= n + 1; ++z) Q[x][y][z] += delta;
  memcpy(T, Q, sizeof(cube));
}
int main() {
  int n;
  scanf("%d", &n);
  if (n == 1) {
    puts("1");
    return 0;
  }
  M[2][1][1][1] = 1;
  M[2][2][1][1] = 2;
  M[2][1][2][1] = 4;
  M[2][2][2][1] = 3;
  M[2][1][2][2] = 5;
  M[2][2][2][2] = 6;
  M[2][1][1][2] = 8;
  M[2][2][1][2] = 7;
  for (int i = 2; i < n; ++i)
    if (i & 1)
      expandOdd(i, M[i], M[i + 1]);
    else
      expandEven(i, M[i], M[i + 1]);
  for (int i = 1; i <= n; ++i) viewLayer(M[n], n, -1, -1, i), puts("");
  return 0;
}