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 = 105;
inline int gi() {
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  int sum = 0;
  while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
  return sum;
}
int n, A[maxn][maxn][maxn];
int main() {
  n = gi();
  if (n == 1) return puts("1"), 0;
  A[1][1][1] = 4;
  A[1][1][2] = 1;
  A[1][2][1] = 3;
  A[1][2][2] = 2;
  A[2][1][1] = 5;
  A[2][1][2] = 8;
  A[2][2][1] = 6;
  A[2][2][2] = 7;
  A[3][1][1] = 10;
  A[3][1][2] = 9;
  A[3][2][1] = 11;
  A[3][2][2] = 12;
  for (int i = 3; i <= n; ++i)
    if (i & 1) {
      int p1 = 1;
      for (int j = 1; j <= i; ++j) A[j][1][i] = --p1;
      for (int j = i; j; --j)
        if ((j - i) & 1)
          for (int k = 1; k <= i; ++k) A[j][0][k] = --p1;
        else
          for (int k = i; k; --k) A[j][0][k] = --p1;
      int p2 = A[i][i - 1][i - 1];
      for (int j = i - 1; j >= 2; --j) A[i][j][i] = ++p2;
      for (int j = 2; j < i; ++j)
        if (j & 1)
          for (int k = 1; k < i; ++k) A[k][j][i] = ++p2;
        else
          for (int k = i - 1; k; --k) A[k][j][i] = ++p2;
      for (int j = 1; j <= i; ++j)
        if (j & 1)
          for (int k = i; k; --k) A[j][i][k] = ++p2;
        else
          for (int k = 1; k <= i; ++k) A[j][i][k] = ++p2;
      for (int p = i + 1; p; --p)
        for (int x = 1; x <= i; ++x)
          for (int y = 1; y <= i; ++y) A[x][p][y] = A[x][p - 1][y] - p1 + 1;
      for (int x = 1; x <= i; ++x)
        for (int y = 1; y <= i + 1; ++y)
          for (int z = 1; z * 2 <= i; ++z) swap(A[x][y][z], A[x][y][i + 1 - z]);
    } else {
      int p1 = 1;
      for (int j = 1; j <= i; ++j) A[1][j][i] = --p1;
      for (int j = i; j; --j)
        if ((i - j) & 1)
          for (int k = 1; k <= i; ++k) A[0][j][k] = --p1;
        else
          for (int k = i; k; --k) A[0][j][k] = --p1;
      int p2 = A[i - 1][i][i - 1];
      for (int j = i; j; --j)
        if ((i - j) & 1)
          for (int k = 2; k < i; ++k) A[k][j][i] = ++p2;
        else
          for (int k = i - 1; k >= 2; --k) A[k][j][i] = ++p2;
      for (int j = 1; j <= i; ++j)
        if (j & 1)
          for (int k = i; k; --k) A[i][j][k] = ++p2;
        else
          for (int k = 1; k <= i; ++k) A[i][j][k] = ++p2;
      for (int p = i + 1; p; --p)
        for (int x = 1; x <= i; ++x)
          for (int y = 1; y <= i; ++y) A[p][x][y] = A[p - 1][x][y] - p1 + 1;
    }
  for (int y = 1; y <= n; ++y) {
    for (int z = n; z; --z) {
      for (int x = 1; x <= n; ++x) printf("%d ", A[x][y][z]);
      puts("");
    }
    puts("");
  }
  return 0;
}