Given a positive integer n, print an n x n matrix containing the numbers from 1 to n * n in spiral order, starting at the top-left corner and moving down.

Input

• One positive integer n.

Output

• Numbers on the same line are separated by exactly one space.

Constraints

• 1 <= n <= 30

Example

Input

4

Output

1 12 11 10
2 13 16 9
3 14 15 8
4 5 6 7