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 MAXN = 150;
const int OFFSET = 1000000;
const int INF = 1012345678;
int n, mat[MAXN][MAXN][MAXN];
void output() {
  int startIdx = INF, endIdx;
  for (int x = 0; x < MAXN; x++) {
    for (int y = 0; y < MAXN; y++) {
      for (int z = 0; z < MAXN; z++) {
        if (mat[x][y][z]) {
          startIdx = min(startIdx, mat[x][y][z]);
        }
      }
    }
  }
  endIdx = startIdx + n * n * n - 1;
  int minx = INF, maxx = -INF;
  int miny = INF, maxy = -INF;
  int minz = INF, maxz = -INF;
  for (int x = 0; x < MAXN; x++) {
    for (int y = 0; y < MAXN; y++) {
      for (int z = 0; z < MAXN; z++) {
        if (startIdx <= mat[x][y][z] && mat[x][y][z] <= endIdx) {
          minx = min(minx, x);
          maxx = max(maxx, x);
          miny = min(miny, y);
          maxy = max(maxy, y);
          minz = min(minz, z);
          maxz = max(maxz, z);
        }
      }
    }
  }
  for (int x = minx; x <= maxx; x++) {
    for (int y = miny; y <= maxy; y++) {
      for (int z = minz; z <= maxz; z++) {
        printf("%d%c", mat[x][y][z] - startIdx + 1, z == maxz ? '\n' : ' ');
      }
    }
    if (x != maxx) putchar('\n');
  }
}
struct Point {
  int x, y, z;
  Point() {}
  Point(int x, int y, int z) : x(x), y(y), z(z) {}
  Point operator+(const Point &rhs) const {
    return Point(x + rhs.x, y + rhs.y, z + rhs.z);
  }
  void setPoint(int value) { mat[x][y][z] = value; }
};
const Point IN = Point(-1, 0, 0);
const Point OUT = Point(1, 0, 0);
const Point LEFT = Point(0, -1, 0);
const Point RIGHT = Point(0, 1, 0);
const Point DOWN = Point(0, 0, -1);
const Point UP = Point(0, 0, 1);
void solve() {
  if (n == 1) {
    puts("1");
    return;
  }
  Point head = Point(75, 75, 1), tail = head;
  int headIdx = OFFSET - 1, tailIdx = OFFSET;
  tail.setPoint(tailIdx++);
  tail = tail + IN;
  tail.setPoint(tailIdx++);
  tail = tail + DOWN;
  tail.setPoint(tailIdx++);
  tail = tail + OUT;
  tail.setPoint(tailIdx++);
  tail = tail + RIGHT;
  tail.setPoint(tailIdx++);
  tail = tail + UP;
  tail.setPoint(tailIdx++);
  tail = tail + IN;
  tail.setPoint(tailIdx++);
  tail = tail + DOWN;
  tail.setPoint(tailIdx++);
  tail = tail + RIGHT;
  tail.setPoint(tailIdx++);
  tail = tail + OUT;
  tail.setPoint(tailIdx++);
  tail = tail + UP;
  tail.setPoint(tailIdx++);
  tail = tail + IN;
  tail.setPoint(tailIdx++);
  for (int o = 2; o < n; o++) {
    if (o & 1) {
      head = head + UP;
      head.setPoint(headIdx--);
      for (int i = 0; i < o; i++) {
        head = head + IN;
        head.setPoint(headIdx--);
      }
      head = head + LEFT + IN;
      for (int i = 0; i <= o >> 1; i++) {
        head = head + OUT;
        head.setPoint(headIdx--);
        for (int i = 0; i < o; i++) {
          head = head + DOWN;
          head.setPoint(headIdx--);
        }
        head = head + OUT;
        head.setPoint(headIdx--);
        for (int i = 0; i < o; i++) {
          head = head + UP;
          head.setPoint(headIdx--);
        }
      }
      tail = tail + UP + IN;
      for (int i = 0; i <= o >> 1; i++) {
        tail = tail + OUT;
        tail.setPoint(tailIdx++);
        for (int j = 0; j < o - 2; j++) {
          tail = tail + LEFT;
          tail.setPoint(tailIdx++);
        }
        tail = tail + OUT;
        tail.setPoint(tailIdx++);
        for (int j = 0; j < o - 2; j++) {
          tail = tail + RIGHT;
          tail.setPoint(tailIdx++);
        }
      }
      tail = tail + RIGHT + OUT;
      for (int i = 0; i <= o >> 1; i++) {
        tail = tail + IN;
        tail.setPoint(tailIdx++);
        for (int i = 0; i < o; i++) {
          tail = tail + DOWN;
          tail.setPoint(tailIdx++);
        }
        tail = tail + IN;
        tail.setPoint(tailIdx++);
        for (int i = 0; i < o; i++) {
          tail = tail + UP;
          tail.setPoint(tailIdx++);
        }
      }
    } else {
      head = head + UP;
      head.setPoint(headIdx--);
      for (int i = 0; i < o; i++) {
        head = head + RIGHT;
        head.setPoint(headIdx--);
      }
      head = head + OUT;
      head.setPoint(headIdx--);
      for (int i = 0; i < o; i++) {
        head = head + DOWN;
        head.setPoint(headIdx--);
      }
      for (int i = 0; i < o; i++) {
        head = head + LEFT;
        head.setPoint(headIdx--);
      }
      for (int i = 0; i < o >> 1; i++) {
        head = head + UP;
        head.setPoint(headIdx--);
        for (int j = 0; j < o - 1; j++) {
          head = head + RIGHT;
          head.setPoint(headIdx--);
        }
        head = head + UP;
        head.setPoint(headIdx--);
        for (int j = 0; j < o - 1; j++) {
          head = head + LEFT;
          head.setPoint(headIdx--);
        }
      }
      tail = tail + UP;
      tail.setPoint(tailIdx++);
      for (int i = 0; i < o - 2; i++) {
        tail = tail + OUT;
        tail.setPoint(tailIdx++);
      }
      for (int i = 0; i < o; i++) {
        tail = tail + LEFT;
        tail.setPoint(tailIdx++);
      }
      for (int i = 1; i < o >> 1; i++) {
        tail = tail + IN;
        tail.setPoint(tailIdx++);
        for (int j = 0; j < o - 1; j++) {
          tail = tail + RIGHT;
          tail.setPoint(tailIdx++);
        }
        tail = tail + IN;
        tail.setPoint(tailIdx++);
        for (int j = 0; j < o - 1; j++) {
          tail = tail + LEFT;
          tail.setPoint(tailIdx++);
        }
      }
      tail = tail + IN;
      tail.setPoint(tailIdx++);
      for (int i = 0; i < o; i++) {
        tail = tail + DOWN;
        tail.setPoint(tailIdx++);
      }
      for (int i = 0; i < o; i++) {
        tail = tail + RIGHT;
        tail.setPoint(tailIdx++);
      }
      for (int i = 0; i < o >> 1; i++) {
        tail = tail + UP;
        tail.setPoint(tailIdx++);
        for (int j = 0; j < o - 1; j++) {
          tail = tail + LEFT;
          tail.setPoint(tailIdx++);
        }
        tail = tail + UP;
        tail.setPoint(tailIdx++);
        for (int j = 0; j < o - 1; j++) {
          tail = tail + RIGHT;
          tail.setPoint(tailIdx++);
        }
      }
    }
  }
  output();
}
int main() {
  scanf("%d", &n);
  solve();
  return 0;
}