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>
void re(int& x);
int n;
int cube[71][71][71];
void solve() {
  re(n);
  int max_n = n * n * n;
  int c = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (i % 2 == 0) {
      for (int y = 0; y < i; y++) cube[0][i][y] = ++c;
      for (int x = i; x >= 0; x--) cube[0][x][i] = ++c;
    } else {
      for (int x = 0; x <= i; x++) cube[0][x][i] = ++c;
      for (int y = i - 1; y >= 0; y--) cube[0][i][y] = ++c;
    }
  }
  for (int i = 1; i < n; i++) {
    if (i % 2 == 1) {
      int cl = i, cx = i - 1, cy = i - 1;
      cube[cl][cx][cy] = ++c;
      while (cx > 0) {
        cube[cl][--cx][cy] = ++c;
      }
      for (int xx = 0; xx <= i - 1; xx++) {
        if (xx % 2 == 0)
          for (int y = i - 2; y >= 0; y--) cube[cl][xx][y] = ++c;
        else
          for (int y = 0; y <= i - 2; y++) cube[cl][xx][y] = ++c;
      }
      cx = i;
      cy = 0;
      for (int yy = 0; yy <= i; yy++) {
        if (yy % 2 == 0)
          for (int l = cl; l >= 1; l--) cube[l][cx][yy] = ++c;
        else
          for (int l = 1; l <= cl; l++)
            if (!(yy == i && l != 0)) cube[l][cx][yy] = ++c;
      }
      cx = i;
      cy = i;
      for (int ll = 1; ll <= i; ll++) {
        if (ll % 2 == 1)
          for (int x = i; x >= 0; x--) cube[ll][x][cy] = ++c;
        else
          for (int x = 0; x <= i; x++) cube[ll][x][cy] = ++c;
      }
    } else {
      int cl = i, cx = 0, cy = i - 1;
      for (int xx = 0; xx <= i - 1; xx++) {
        if (xx % 2 == 0)
          for (int y = i - 1; y >= 0; y--) cube[cl][xx][y] = ++c;
        else
          for (int y = 0; y <= i - 1; y++) cube[cl][xx][y] = ++c;
      }
      cx = i;
      for (int ll = i; ll >= 1; ll--) {
        if (ll % 2 == i % 2)
          for (int yy = i - 1; yy >= 0; yy--) cube[ll][cx][yy] = ++c;
        else
          for (int yy = 0; yy <= i - 1; yy++) cube[ll][cx][yy] = ++c;
      }
      cy = 0;
      cx = i, cy = i;
      for (int ll = 1; ll <= i; ll++) {
        if (ll % 2 == 1)
          for (int x = i; x >= 0; x--) cube[ll][x][cy] = ++c;
        else
          for (int x = 0; x <= i; x++) cube[ll][x][cy] = ++c;
      }
    }
  }
  for (int layer = 0; layer < n; layer++) {
    for (int x = 0; x < n; x++) {
      for (int y = 0; y < n; y++) {
        printf("%d ", cube[layer][x][y]);
      }
      printf("\n");
    }
    printf("\n");
  }
}
int main() { solve(); }
void re(int& x) { scanf("%d", &x); }