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

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 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7