Magic Odd Square

Find an n × n matrix with different numbers from 1 to n ², so the sum in each row, column and both main diagonals are odd.

Input

The only line contains odd integer n (1 ≤ n ≤ 49).

Output

Print n lines with n integers. All the integers should be different and from 1 to n ². The sum in each row, column and both main diagonals should be odd.

Examples

input

1

output

1

input

3

output

2 1 4
3 5 7
6 9 8

Solution:

#include <bits/stdc++.h>

using namespace std;

const int N = 1234;

int a[N][N], b[N][N];

int main() {
int n;
scanf("%d", &n);
a[0][0] = 1;
int k = 1;
while (k < n) {
    memset(b, 255, sizeof(b));
    for (int i = 0; i < k; i++) {
      for (int j = 0; j < k; j++) {
        b[i + 1][j + 1] = a[i][j];
      }
    }
    int ptr = k * k;
    for (int i = 1; i <= k; i++) {
      b[i][0] = (ptr += 2);
      b[i][k + 1] = (ptr += 2);
    }
    b[0][k / 2 + 1] = (ptr += 2);
    b[k + 1][k / 2 + 1] = (ptr += 2);
    ptr = k * k - 1;
    k += 2;
    for (int i = 0; i < k; i++) {
      for (int j = 0; j < k; j++) {
        a[i][j] = b[i][j];
        if (a[i][j] == -1) {
          a[i][j] = (ptr += 2);
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (j > 0) {
putchar(' ');
}
printf("%d", a[i][j]);
}
puts("");
}
return 0;
}