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 V = 53;
int sqr(int x) { return x * x; }
int a[V][V][V][V], te[V][V][V];
int n, i, j, k, nx, ny, nz, dr, d, ct;
int main() {
  a[1][1][1][1] = 1;
  a[2][1][1][1] = 1;
  a[2][1][2][1] = 4;
  a[2][2][1][1] = 2;
  a[2][2][2][1] = 3;
  a[2][1][1][2] = 8;
  a[2][1][2][2] = 5;
  a[2][2][1][2] = 7;
  a[2][2][2][2] = 6;
  for (n = 2; n <= 50; n++) {
    d = sqr(n);
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        for (k = 1; k <= n; k++) a[n + 1][i][j][k + 1] = a[n][i][j][k] + d;
    nx = 1;
    ny = n;
    nz = 1;
    dr = 1;
    ct = 1;
    if (n % 2 == 0) {
      while (1) {
        if (ny < 1) break;
        a[n + 1][nx][ny][nz] = ct;
        ct++;
        if (nx + dr < 1 || nx + dr > n)
          dr *= -1, ny--;
        else
          nx += dr;
      }
    } else {
      while (1) {
        if (ny == n - 1) break;
        a[n + 1][nx][ny][nz] = ct;
        ct++;
        if (nx + dr < 1 || nx + dr > n)
          dr *= -1, ny--;
        else
          nx += dr;
      }
      while (1) {
        if (nx < 1) break;
        a[n + 1][nx][ny][nz] = ct;
        ct++;
        if (ny + dr < 1 || ny + dr > n - 1)
          dr *= -1, nx--;
        else
          ny += dr;
      }
    }
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        for (k = 1; k <= n + 1; k++) te[n + 1 - j][i][k] = a[n + 1][i][j][k];
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        for (k = 1; k <= n + 1; k++) a[n + 1][i][j][k] = te[i][j][k];
    ct = n * n * n + d + 1;
    nx = n + 1;
    ny = 1;
    nz = n + 1;
    dr = -1;
    while (1) {
      if (ny > n + 1) break;
      a[n + 1][nx][ny][nz] = ct;
      ct++;
      if (nz + dr < 1 || nz + dr > n + 1)
        dr *= -1, ny++;
      else
        nz += dr;
    }
    ny--;
    nx--;
    while (1) {
      if (nx < 1) break;
      a[n + 1][nx][ny][nz] = ct;
      ct++;
      if (nz + dr < 1 || nz + dr > n + 1)
        dr *= -1, nx--;
      else
        nz += dr;
    }
    for (i = 1; i <= n + 1; i++)
      for (j = 1; j <= n + 1; j++)
        for (k = 1; k <= n + 1; k++) te[i][k][j] = a[n + 1][i][j][k];
    for (i = 1; i <= n + 1; i++)
      for (j = 1; j <= n + 1; j++)
        for (k = 1; k <= n + 1; k++) a[n + 1][i][j][k] = te[i][j][k];
  }
  while (~scanf("%d", &n)) {
    for (i = 1; i <= n; i++) {
      for (j = 1; j <= n; j++) {
        for (k = 1; k <= n; k++) {
          if (k != 1) printf(" ");
          printf("%d", a[n][j][k][i]);
        }
        puts("");
      }
      puts("");
    }
  }
}