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>
int a[55][55][55];
void cube(int siz, int& num, int& x, int& y, int& z) {
  if (siz == 1) {
    a[x][y][++z] = ++num;
  } else if (siz & 1) {
    for (int i = 1; i <= siz; i++) a[x][y][++z] = ++num;
    for (int i = 1; i < siz; i++) a[x][++y][z] = ++num;
    cube(--siz, num, x, y, z), ++x, ++z;
    for (int i = 1; i <= siz; i++) a[x][y][--z] = ++num;
    for (int i = 1; i <= siz; i++) {
      if (i & 1) {
        for (int j = 1; j < siz; j++) a[x][--y][z] = ++num;
      } else {
        for (int j = 1; j < siz; j++) a[x][y++][z] = ++num;
      }
      ++z;
    }
    for (int i = 1; i <= siz; i++) {
      if (i & 1) {
        for (int j = 1; j <= siz; j++) a[x][--y][z] = ++num;
        for (int j = 1; j <= siz; j++) a[x][y][--z] = ++num;
      } else {
        for (int j = 1; j <= siz; j++) a[x][y][z++] = ++num;
        for (int j = 1; j <= siz; j++) a[x][y++][z] = ++num;
      }
      --x;
    }
    for (int i = 1; i <= siz; i++) a[++x][y][z] = ++num;
  } else {
    for (int i = 1; i <= siz; i++) a[x][y][--z] = ++num;
    for (int i = 1; i < siz; i++) a[x][--y][z] = ++num;
    cube(--siz, num, x, y, z), ++x, ++y;
    for (int i = 1; i <= siz; i++) {
      if (i & 1) {
        for (int j = 1; j <= siz; j++) a[x][--y][z] = ++num;
      } else {
        for (int j = 1; j <= siz; j++) a[x][y++][z] = ++num;
      }
      --z;
    }
    for (int i = 1; i <= siz; i++) {
      if (i & 1) {
        for (int j = 1; j <= siz; j++) a[x][y++][z] = ++num;
        for (int j = 1; j <= siz; j++) a[x][y][z++] = ++num;
      } else {
        for (int j = 1; j <= siz; j++) a[x][y][--z] = ++num;
        for (int j = 1; j <= siz; j++) a[x][--y][z] = ++num;
      }
      --x;
    }
    for (int i = 1; i <= siz; i++) a[++x][y][z] = ++num;
  }
  return;
}
int main() {
  int n, m, x, y, z;
  scanf("%d", &n);
  if (n & 1)
    m = 0, x = 1, y = z = 0, cube(n, m, x, ++y, z);
  else
    m = 0, x = 1, y = z = n, cube(n, m, x, y, ++z);
  for (x = 1; x <= n; putchar('\n'), x++)
    for (y = 1; y <= n; putchar('\n'), y++)
      for (z = 1; z <= n; putchar(' '), z++) printf("%d", a[x][y][z]);
  return 0;
}