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 v[100][100][100];
int main() {
  int n, i, j, k, mn, dif, f, s;
  scanf("%d", &n);
  if (n == 1) {
    printf("1");
    return 0;
  }
  v[1][1][2] = 1;
  v[1][1][1] = 2;
  v[1][2][1] = 3;
  v[1][2][2] = 4;
  v[2][2][2] = 5;
  v[2][2][1] = 6;
  v[2][1][1] = 7;
  v[2][1][2] = 8;
  for (i = 3; i <= n; i++) {
    if (i & 1) {
      f = v[1][1][i - 1] - 1;
      for (j = 1; j <= i; j++) v[1][j][i] = f--;
      for (j = i - 1; j > 0; j--) v[1][i][j] = f--;
    } else {
      f = v[1][i - 1][1] - 1;
      for (j = 1; j <= i; j++) v[1][i][j] = f--;
      for (j = i - 1; j > 0; j--) v[1][j][i] = f--;
    }
    f = v[i - 1][1][i - 1] + 1;
    if (!(i & 1)) {
      for (j = 1; j < i; j++) {
        if (j & 1)
          for (k = i - 1; k > 0; k--) v[i][j][k] = f++;
        else
          for (k = 1; k < i; k++) v[i][j][k] = f++;
      }
      for (k = i; k > 1; k--) v[k][i][1] = f++;
      for (k = 2; k <= i; k++) {
        if (k & 1) {
          for (j = 1; j <= i; j++) v[k][j][i] = f++;
          for (j = i - 1; j > 1; j--) v[k][i][j] = f++;
        } else {
          for (j = 2; j <= i; j++) v[k][i][j] = f++;
          for (j = i - 1; j > 0; j--) v[k][j][i] = f++;
        }
      }
    } else {
      for (j = 1; j < i; j++) {
        if (j & 1)
          for (k = i - 1; k > 0; k--) v[i][j][k] = f++;
        else
          for (k = 1; k < i; k++) v[i][j][k] = f++;
      }
      for (k = i; k > 1; k--) {
        if (k & 1)
          for (j = i - 1; j > 0; j--) v[k][i][j] = f++;
        else
          for (j = 1; j < i; j++) v[k][i][j] = f++;
      }
      for (k = i; k > 0; k--) {
        if (k & 1)
          for (j = 2; j <= i; j++) v[j][k][i] = f++;
        else
          for (j = i; j > 1; j--) v[j][k][i] = f++;
      }
    }
  }
  mn = 1;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      for (k = 1; k <= n; k++)
        if (v[i][j][k] < mn) mn = v[i][j][k];
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      for (k = 1; k <= n; k++) v[i][j][k] += 1 - mn;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      for (k = 1; k <= n; k++) printf("%d ", v[i][j][k]);
      putchar('\n');
    }
    putchar('\n');
  }
}