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 n, i, j, k, now, a1, b1, c1, a2, b2, c2, id1, id2;
int id[55][55][55];
void F1() { id[++a1][b1][c1] = ++id1; }
void B1() { id[--a1][b1][c1] = ++id1; }
void U1() { id[a1][++b1][c1] = ++id1; }
void D1() { id[a1][--b1][c1] = ++id1; }
void L1() { id[a1][b1][--c1] = ++id1; }
void R1() { id[a1][b1][++c1] = ++id1; }
void F2() { id[++a2][b2][c2] = --id2; }
void B2() { id[--a2][b2][c2] = --id2; }
void U2() { id[a2][++b2][c2] = --id2; }
void D2() { id[a2][--b2][c2] = --id2; }
void L2() { id[a2][b2][--c2] = --id2; }
void R2() { id[a2][b2][++c2] = --id2; }
int main() {
  scanf("%d", &n);
  if (n == 1) {
    printf("1\n");
    return 0;
  }
  id[a1 = 2][b1 = 1][c1 = 1] = id1 = 1;
  id[a2 = 1][b2 = 1][c2 = 1] = id2 = 0;
  U2();
  R2();
  D2();
  R1();
  U1();
  L1();
  for (now = 2; now < n; ++now) {
    if (now % 2) {
      F1();
      for (i = 1; i < now; ++i) L1();
      D1();
      for (i = 1; i <= now; ++i) {
        for (j = 2; j < now; ++j)
          if (i % 2)
            D1();
          else
            U1();
        R1();
      }
      for (i = 1; i <= now; ++i) {
        for (j = 1; j < now; ++j)
          if (i % 2)
            B1();
          else
            F1();
        U1();
      }
      for (i = 1; i <= now; ++i) {
        for (j = 1; j <= now; ++j)
          if (i % 2)
            L1();
          else
            R1();
        if (i != now) F1();
      }
    } else {
      F1();
      for (i = 1; i <= now; ++i) {
        for (j = 1; j < now; ++j)
          if (i % 2)
            D1();
          else
            U1();
        R1();
      }
      for (i = 1; i <= now; ++i) {
        for (j = 1; j < now; ++j)
          if (i % 2)
            D1();
          else
            U1();
        if (i != now) B1();
      }
      U1();
      for (i = 1; i <= now; ++i) {
        for (j = 1; j <= now; ++j)
          if (i % 2)
            L1();
          else
            R1();
        if (i != now) F1();
      }
    }
    if (now % 2) {
      U2();
      for (i = 1; i <= now; ++i) R2();
      for (i = 1; i <= now; ++i) D2();
    } else {
      R2();
      for (i = 1; i <= now; ++i) U2();
      for (i = 1; i <= now; ++i) L2();
    }
  }
  for (i = 1; i <= n; ++i) {
    for (j = 1; j <= n; ++j) {
      for (k = 1; k <= n; ++k) {
        printf("%d", id[i][j][k] - id2 + 1);
        if (k != n) printf(" ");
      }
      printf("\n");
    }
    if (i != n) printf("\n");
  }
}