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;
vector<vector<vector<int> > > genera(int n) {
  vector<vector<vector<int> > > v(
      n + 1, vector<vector<int> >(n + 1, vector<int>(n + 1)));
  if (n == 1) {
    v[1][1][1] = 1;
    return v;
  }
  int color = 1;
  if (n == 2) {
    v[1][1][1] = color++;
    v[1][2][1] = color++;
    v[2][2][1] = color++;
    v[2][2][2] = color++;
    v[1][2][2] = color++;
    v[1][1][2] = color++;
    v[2][1][2] = color++;
    v[2][1][1] = color++;
    return v;
  }
  int i, j, k;
  i = j = k = 1;
  if ((n - 1) % 2 == 0) {
    while (j < n - 1) {
      for (; i <= n - 1; i++) v[i][j][k] = color++;
      i = n - 1;
      j++;
      for (; i >= 1; i--) v[i][j][k] = color++;
      i = 1;
      j++;
    }
  } else {
    for (; i <= n - 1; i++) v[i][j][k] = color++;
    i = n - 1;
    for (j = 2; j <= n - 1; j++) v[i][j][k] = color++;
    i = n - 2;
    j = n - 1;
    while (i > 1) {
      for (; j >= 2; j--) v[i][j][k] = color++;
      j = 2;
      i--;
      for (; j <= n - 1; j++) v[i][j][k] = color++;
      j = n - 1;
      i--;
    }
  }
  i = 1;
  j = n - 1;
  k = 2;
  int top = n - 1;
  int pas = 0;
  while (top >= 2) {
    if (pas % 2 == 0) {
      i = 1;
      j = top;
      for (k = 2; k <= top; k++) v[i][j][k] = color++;
      k = top;
      for (j = top - 1; j >= 1; j--) v[i][j][k] = color++;
      j = 1;
      for (i = 2; i <= top; i++) v[i][j][k] = color++;
      i = top;
    } else {
      j = 1;
      i = top;
      for (k = 2; k <= top; k++) v[i][j][k] = color++;
      k = top;
      for (i = top - 1; i >= 1; i--) v[i][j][k] = color++;
      i = 1;
      for (j = 2; j <= top; j++) v[i][j][k] = color++;
      j = top;
    }
    for (k = top - 1; k >= 2; k--) v[i][j][k] = color++;
    k = 2;
    top--;
    pas++;
  }
  vector<vector<vector<int> > > vinf = genera(n - 1);
  for (int ii = 1; ii <= n - 1; ii++)
    for (int jj = 1; jj <= n - 1; jj++)
      for (int kk = 1; kk <= n - 1; kk++)
        v[ii + 1][jj + 1][kk + 1] = vinf[ii][jj][kk] + color - 1;
  color += (n - 1) * (n - 1) * (n - 1);
  i = n;
  j = 2;
  k = 1;
  for (; j <= n; j++) v[i][j][k] = color++;
  j = n;
  i--;
  for (; i >= 1; i--) v[i][j][k] = color++;
  i = 1;
  k++;
  for (; k <= n; k++) v[i][j][k] = color++;
  k = n;
  j--;
  for (; j >= 1; j--) v[i][j][k] = color++;
  j = 1;
  i++;
  for (; i <= n; i++) v[i][j][k] = color++;
  i = n;
  k--;
  for (; k >= 1; k--) v[i][j][k] = color++;
  return v;
}
int main() {
  int n;
  cin >> n;
  vector<vector<vector<int> > > v = genera(n);
  for (int k = 1; k <= n; k++) {
    if (k > 1) cout << endl;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (j > 1) cout << " ";
        cout << v[i][j][k];
      }
      cout << endl;
    }
  }
}