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[52][52][52][52], tmp[52][52][52];
int main() {
  a[1][1][1][1] = 1;
  a[2][1][1][1] = 4;
  a[2][2][1][1] = 3;
  a[2][1][2][1] = 1;
  a[2][2][2][1] = 2;
  a[2][1][1][2] = 5;
  a[2][2][1][2] = 6;
  a[2][1][2][2] = 8;
  a[2][2][2][2] = 7;
  for (int n = 2; n < 50; n++) {
    for (int x = 1; x <= n; x++)
      for (int y = 1; y <= n; y++)
        for (int z = 1; z <= n; z++)
          a[n + 1][x][y][z + 1] = a[n][x][y][z] + n * n;
    if (n & 1) {
      int cnt = 0;
      for (int y = 1; y <= n - 2; y++) {
        if (y & 1)
          for (int x = 1; x <= n; x++) a[n + 1][x][y][1] = ++cnt;
        else
          for (int x = n; x >= 1; x--) a[n + 1][x][y][1] = ++cnt;
      }
      for (int x = n; x >= 1; x--)
        if (x & 1) {
          a[n + 1][x][n - 1][1] = ++cnt;
          a[n + 1][x][n][1] = ++cnt;
        } else {
          a[n + 1][x][n][1] = ++cnt;
          a[n + 1][x][n - 1][1] = ++cnt;
        }
    } else {
      int cnt = 0;
      for (int y = 1; y <= n; y++) {
        if (y & 1)
          for (int x = 1; x <= n; x++) a[n + 1][x][y][1] = ++cnt;
        else
          for (int x = n; x >= 1; x--) a[n + 1][x][y][1] = ++cnt;
      }
    }
    int cnt = n * n * (n + 1);
    for (int x = 1; x <= n + 1; x++) {
      if (x & 1)
        for (int z = n + 1; z >= 1; z--) a[n + 1][x][n + 1][z] = ++cnt;
      else
        for (int z = 1; z <= n + 1; z++) a[n + 1][x][n + 1][z] = ++cnt;
    }
    for (int y = n; y >= 1; y--) {
      if ((n + 1 + (n - y + 1)) & 1)
        for (int z = n + 1; z >= 1; z--) a[n + 1][n + 1][y][z] = ++cnt;
      else
        for (int z = 1; z <= n + 1; z++) a[n + 1][n + 1][y][z] = ++cnt;
    }
    for (int x = 1; x <= n + 1; x++)
      for (int y = 1; y <= n + 1; y++)
        for (int z = 1; z <= n + 1; z++)
          tmp[n - z + 2][y][x] = a[n + 1][x][y][z];
    memcpy(a[n + 1], tmp, sizeof(tmp));
    for (int rep = 0; rep < 2; rep++) {
      for (int x = 1; x <= n + 1; x++)
        for (int y = 1; y <= n + 1; y++)
          for (int z = 1; z <= n + 1; z++)
            tmp[y][n - x + 2][z] = a[n + 1][x][y][z];
      memcpy(a[n + 1], tmp, sizeof(tmp));
    }
    assert(a[n + 1][1][n + 1][n + 1] == (n + 1) * (n + 1) * (n + 1));
    assert(a[n + 1][1][n + 1][1] == 1);
  }
  int m;
  scanf("%d", &m);
  for (int i = 1; i <= m; i++, puts(""))
    for (int j = 1; j <= m; j++, puts(""))
      for (int k = 1; k <= m; k++) printf("%d ", a[m][i][j][k]);
}