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[64][64];
int R[64][64][64];
int T[64][64][64];
int F(int n, int m, int cnt) {
  int i, j;
  int pos = 0;
  for (i = (0); i < (n); ++i) {
    if (pos == 0)
      for (j = (0); j < (m); ++j) {
        A[i][j] = cnt;
        ++cnt;
      }
    else
      for (j = (m)-1; j >= (0); --j) {
        A[i][j] = cnt;
        ++cnt;
      }
    pos = m - 1 - pos;
  }
  return cnt;
}
void F(int n) {
  int i, j, k;
  if (n & 1) {
    for (i = (0); i < (n); ++i)
      for (j = (0); j < (n); ++j)
        for (k = (0); k < (n); ++k) T[i + 1][j + 1][k + 1] = R[i][j][k] + n * n;
    int cnt = F(n, n, 0) + n * n * n;
    for (i = (0); i < (n); ++i)
      for (j = (0); j < (n); ++j) T[0][n - i][n - j] = A[i][j];
    cnt = F(n + 1, n, cnt);
    for (i = (0); i < (n + 1); ++i)
      for (j = (0); j < (n); ++j) T[n - i][0][j + 1] = A[i][j];
    cnt = F(n + 1, n + 1, cnt);
    for (i = (0); i < (n + 1); ++i)
      for (j = (0); j < (n + 1); ++j) T[j][i][0] = A[i][j];
    for (i = (0); i < (n + 1); ++i)
      for (j = (0); j < (n + 1); ++j)
        for (k = (0); k < (n + 1); ++k) R[i][j][k] = T[k][n - j][n - i];
  } else {
    for (i = (0); i < (n); ++i)
      for (j = (0); j < (n); ++j)
        for (k = (0); k < (n); ++k) T[i + 1][j + 1][k] = R[i][j][k] + n * n;
    int cnt = F(n, n, 0) + n * n * n;
    for (i = (0); i < (n); ++i)
      for (j = (0); j < (n); ++j) T[0][n - i][j] = A[i][j];
    cnt = F(n, n + 1, cnt);
    for (i = (0); i < (n); ++i)
      for (j = (0); j < (n + 1); ++j) T[n - j][0][i] = A[i][j];
    cnt = F(n + 1, n + 1, cnt);
    for (i = (0); i < (n + 1); ++i)
      for (j = (0); j < (n + 1); ++j) T[n - j][i][n] = A[i][j];
    for (i = (0); i < (n + 1); ++i)
      for (j = (0); j < (n + 1); ++j)
        for (k = (0); k < (n + 1); ++k) R[i][j][k] = T[k][n - j][i];
  }
}
int main() {
  memset(R, -1, sizeof(R));
  int n;
  scanf("%d", &n);
  R[0][0][0] = 0;
  int i, j, k;
  for (i = (1); i < (n); ++i) F(i);
  for (i = (0); i < (n); ++i) {
    for (j = (0); j < (n); ++j)
      for (k = (0); k < (n); ++k)
        printf("%d%c", R[i][j][k] + 1, k == n - 1 ? '\n' : ' ');
    if (i != n - 1) printf("\n");
  }
  return 0;
};