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;
template <typename T, typename U>
inline void smin(T &a, const U &b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, const U &b) {
  if (a < b) a = b;
}
struct point {
  int x, y, z;
  point(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) {}
} ST, ED;
deque<point> q;
int ans[102][102][102], N;
inline void st(int x, int y, int z) {
  ST.x += x, ST.y += y, ST.z += z;
  q.push_front(ST);
}
inline void ed(int x, int y, int z) {
  ED.x += x, ED.y += y, ED.z += z;
  q.push_back(ED);
}
inline void update_1() {
  st(0, 0, 1);
  for (int i = N; i--;) st(0, 1, 0);
  ed(0, 0, 1);
  for (int i = 0; i < N + 1; i++) {
    if (i & 1)
      for (int j = N - 2; j--;) ed(-1, 0, 0);
    else
      for (int j = N - 2; j--;) ed(1, 0, 0);
    if (i < N) ed(0, -1, 0);
  }
  st(1, 0, 0);
  for (int i = 0; i < N + 1; i++) {
    if (i & 1)
      for (int j = N; j--;) st(0, 0, 1);
    else
      for (int j = N; j--;) st(0, 0, -1);
    if (i < N) st(0, -1, 0);
  }
}
inline void two_1() {
  ed(-1, 0, 0);
  for (int i = 0; i < N + 1; i++) {
    if (i & 1)
      for (int j = N; j--;) ed(0, 0, 1);
    else
      for (int j = N; j--;) ed(0, 0, -1);
    if (i < N) ed(0, 1, 0);
  }
}
inline void update_2() {
  st(0, 0, 1);
  for (int i = N; i--;) st(-1, 0, 0);
  st(0, -1, 0);
  for (int i = 0; i < N + 1; i++) {
    if (i & 1)
      for (int j = N - 1; j--;) st(-1, 0, 0);
    else
      for (int j = N - 1; j--;) st(1, 0, 0);
    if (i < N)
      st(0, 0, -1);
    else
      st(1, 0, 0);
  }
  for (int i = N; i--;) st(0, 0, 1);
  ed(0, 0, 1);
  for (int i = 0; i < N - 1; i++) {
    if (i & 1)
      for (int j = N - 1; j--;) ed(-1, 0, 0);
    else
      for (int j = N - 1; j--;) ed(1, 0, 0);
    if (i < N - 2)
      ed(0, -1, 0);
    else
      ed(1, 0, 0);
  }
  for (int i = N - 2; i--;) ed(0, 1, 0);
}
inline void two_2() {
  ed(0, 1, 0);
  for (int i = 0; i < N + 1; i++) {
    if (i & 1)
      for (int j = N - 1; j--;) ed(1, 0, 0);
    else
      for (int j = N - 1; j--;) ed(-1, 0, 0);
    if (i < N)
      ed(0, 0, -1);
    else
      ed(-1, 0, 0);
  }
  for (int i = N; i--;) ed(0, 0, 1);
}
int main() {
  int n;
  scanf("%d", &n);
  if (n == 1) return puts("1");
  q.push_back(ST);
  ed(0, 0, -1), ed(0, 1, 0), ed(0, 0, 1);
  ed(-1, 0, 0), ed(0, 0, -1), ed(0, -1, 0), ed(0, 0, 1);
  if (n > 2) ed(-1, 0, 0), ed(0, 0, -1), ed(0, 1, 0), ed(0, 0, 1);
  for (N = 2; N < n; N++) {
    N & 1 ? update_1() : update_2();
    if (N == n - 1) break;
    N & 1 ? two_1() : two_2();
  }
  int xmn = 102, ymn = 102, zmn = 102, xmx = 0, ymx = 0, zmx = 0;
  for (int i = 0; i < q.size(); i++) {
    int x = 51 + q[i].x, y = 51 + q[i].y, z = 51 + q[i].z;
    smin(xmn, x), smin(ymn, y), smin(zmn, z);
    smax(xmx, x), smax(ymx, y), smax(zmx, z);
    ans[x][y][z] = i + 1;
  }
  for (int i = zmn; i <= zmx; i++) {
    for (int j = xmn; j <= xmx; j++) {
      for (int k = ymn; k <= ymx; k++) printf("%d ", ans[j][k][i]);
      puts("");
    }
    puts("");
  }
}