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 = 54;
int a[N][N][N];
void go_odd(int n) {
  for (int i = n - 1; i > 0; i--)
    for (int j = 0; j < n - 1; j++)
      for (int k = 0; k < n - 1; k++)
        a[i][j][k] = a[i - 1][j][k] + (n - 1) * (n - 1);
  int st = 1;
  for (int k = 0; k < n - 1; k++) {
    if (k % 2)
      for (int j = n - 2; j >= 0; j--) a[0][j][k] = st++;
    else
      for (int j = 0; j < n - 1; j++) a[0][j][k] = st++;
  }
  st += (n - 1) * (n - 1) * (n - 1);
  for (int j = 0; j < n - 1; j++) {
    if (j % 2)
      for (int i = 0; i < n; i++) a[i][j][n - 1] = st++;
    else
      for (int i = n - 1; i >= 0; i--) a[i][j][n - 1] = st++;
  }
  for (int i = n - 1; i >= 0; i--) {
    if (i % 2)
      for (int k = 1; k < n; k++) a[i][n - 1][k] = st++;
    else
      for (int k = n - 1; k > 0; k--) a[i][n - 1][k] = st++;
  }
  for (int i = 0; i < n; i++) a[i][n - 1][0] = st++;
}
void go_even(int n) {
  for (int i = 0; i < n - 1; i++)
    for (int j = n - 1; j > 0; j--)
      for (int k = n - 1; k > 0; k--)
        a[i][j][k] = a[i][j - 1][k - 1] + (n - 1) * (n - 1);
  int st = 1;
  for (int i = 0; i < n - 1; i++) {
    if (i % 2)
      for (int k = 2; k < n; k++) a[i][0][k] = st++;
    else
      for (int k = n - 1; k > 1; k--) a[i][0][k] = st++;
  }
  for (int i = n - 2; i >= 0; i--) a[i][0][1] = st++;
  st += (n - 1) * (n - 1) * (n - 1);
  for (int j = n - 1; j >= 0; j--) {
    if (j % 2)
      for (int i = n - 2; i >= 0; i--) a[i][j][0] = st++;
    else
      for (int i = 0; i < n - 1; i++) a[i][j][0] = st++;
  }
  for (int k = 0; k < n; k++)
    if (k % 2)
      for (int j = n - 1; j >= 0; j--) a[n - 1][j][k] = st++;
    else
      for (int j = 0; j < n; j++) a[n - 1][j][k] = st++;
}
void go(int n) {
  if (n == 1) {
    a[0][0][0] = 1;
    return;
  }
  go(n - 1);
  if (n % 2)
    go_odd(n);
  else
    go_even(n);
}
int main() {
  int n;
  cin >> n;
  go(n);
  for (int i = n - 1; i >= 0; i--) {
    for (int j = n - 1; j >= 0; j--) {
      for (int k = 0; k < n; k++) printf("%d ", a[j][k][i]);
      printf("\n");
    }
    printf("\n");
  }
}