Egor wants to achieve a rating of 1600 points on the well-known chess portal ChessForces and he needs your help!

Before you start solving the problem, Egor wants to remind you how the chess pieces move. Chess rook moves along straight lines up and down, left and right, as many squares as it wants. And when it wants, it can stop. The queen walks in all directions vertically and diagonally at any distance. You can see the examples below. [Image] 

To reach the goal, Egor should research the next topic:

There is an $N \times N$ board. Each cell of the board has a number from $1$ to $N ^ 2$ in it and numbers in all cells are distinct.

In the beginning, some chess figure stands in the cell with the number $1$. Note that this cell is already considered as visited. After that every move is determined by the following rules:   Among all not visited yet cells to which the figure can get in one move, it goes to the cell that has minimal number. If all accessible cells were already visited and some cells are not yet visited, then the figure is teleported to the not visited cell that has minimal number. If this step happens, the piece pays a fee of $1$ vun. If all cells are already visited, the process is stopped. 

Egor should find an $N \times N$ board on which the rook pays strictly less vuns than the queen during the round with this numbering. Help him to find such $N \times N$ numbered board, or tell that it doesn't exist.


-----Input-----

The only line contains one integer $N$  — the size of the board, $1\le N \le 500$.


-----Output-----

The output should contain $N$ lines.

In $i$-th line output $N$ numbers  — numbers on the $i$-th row of the board. All numbers from $1$ to $N \times N$ must be used exactly once.

On your board rook must pay strictly less vuns than the queen.

If there are no solutions, print $-1$.

If there are several solutions, you can output any of them. 


-----Examples-----
Input
1

Output
-1
Input
4

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



-----Note-----

In case we have $1 \times 1$ board, both rook and queen do not have a chance to pay fees.

In second sample rook goes through cells $1 \to 3 \to 4 \to 6 \to 9 \to 5 \to 7 \to 13 \to 2 \to 8 \to 16 \to 11 \to 10 \to 12 \to 15 \to \textbf{(1 vun)} \to 14$. 

Queen goes through $1 \to 3 \to 4 \to 2 \to 5 \to 6 \to 9 \to 7 \to 13 \to 8 \to 11 \to 10 \to 12 \to 15 \to \textbf{(1 vun)} \to 14 \to \textbf{(1 vun)} \to 16$.

As a result rook pays 1 vun and queen pays 2 vuns.

Difficulty: MEDIUM

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def print_ans(A):
	for a in A:
		print(' '.join(map(str, a)))
N = int(input())
if N <= 2:
	print(-1)
	return
if N == 3:
	A = [[1, 4, 9], [8, 3, 7], [2, 5, 6]]
	print_ans(A)
	return
A = [[4, 3, 6, 12], [7, 5, 9, 15], [14, 1, 11, 10], [13, 8, 16, 2]]
if N == 4:
	print_ans(A)
	return
A[0] += [1]
A[1] += [2]
A[2] += [3]
A[3] += [4]
A.append([8, 9, 6, 7, 5])
for y in range(4):
	for x in range(4):
		A[y][x] += 9
for y in range(5):
	for x in range(5):
		A[y][x] += N * N - 25
	A[y] += [-1] * (N - 5)
for y in range(5, N):
	A += [[-1] * N]
f = True
num = N * N - 25
for i in range(5, N):
	if f:
		for y in range(i):
			A[y][i] = num
			num -= 1
		for x in range(i, -1, -1):
			A[i][x] = num
			num -= 1
	else:
		for x in range(i):
			A[i][x] = num
			num -= 1
		for y in range(i, -1, -1):
			A[y][i] = num
			num -= 1
	f = not f
print_ans(A)


def main():
	for _ in inputt(1):
		(n,) = inputi()
		if n <= 2:
			print(-1)
			continue
		A = [[0] * n for i in range(n)]
		yie = count(1)
		for a in range(n - 3):
			for b in range(a, n)[::-1]:
				A[a][b] = next(yie)
			for b in range(a + 1, n)[::-1]:
				A[b][a] = next(yie)
		A[n - 3][n - 3] = next(yie)
		A[n - 3][n - 2] = next(yie)
		A[n - 1][n - 2] = next(yie)
		A[n - 1][n - 3] = next(yie)
		A[n - 2][n - 2] = next(yie)
		A[n - 2][n - 1] = next(yie)
		A[n - 3][n - 1] = next(yie)
		A[n - 2][n - 3] = next(yie)
		A[n - 1][n - 1] = next(yie)
		for a in A:
			print(*a)
import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	for x in args:
		file.write(str(x))
	file.write(kwargs.pop('end', '\n'))
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inputt = lambda t=0: range(t) if t else range(int(input()))
inputi = lambda : map(int, input().split())
inputl = lambda : list(inputi())
from math import *
from heapq import *
from bisect import *
from itertools import *
from functools import reduce, lru_cache
from collections import Counter, defaultdict
import re, copy, operator, cmath
from builtins import *
main()


n = int(input())
if n < 3:
	print(-1)
else:
	ans = [[-1 for _ in range(n)] for _ in range(n)]
	b = n * n - 9
	ans[0][0] = b + 9
	ans[0][1] = b + 6
	ans[0][2] = b + 7
	ans[1][0] = b + 5
	ans[1][1] = b + 3
	ans[1][2] = b + 8
	ans[2][0] = b + 1
	ans[2][1] = b + 2
	ans[2][2] = b + 4
	for i in range(3, n):
		if i & 1:
			for j in range(i + 1):
				ans[i][j] = n * n - i * i - j
			for j in range(i - 1, -1, -1):
				ans[j][i] = n * n - (i + 1) * (i + 1) + j + 1
		else:
			for j in range(i + 1):
				ans[j][i] = n * n - i * i - j
			for j in range(i - 1, -1, -1):
				ans[i][j] = n * n - (i + 1) * (i + 1) + j + 1
	for x in ans:
		print(*x)


n = int(input())
a = [[0 for j in range(n)] for i in range(n)]
z = 1

def prt(a, n):
	for i in range(n):
		print(*a[i])
if n == 3:
	a = [[7, 1, 9], [8, 6, 5], [3, 2, 4]]
	prt(a, n)
elif n < 4:
	print(-1)
elif n == 4:
	a[0] = [1, 2, 3, 4]
elif n % 2 == 1:
	for i in range(n - 3):
		for j in range(n):
			if i % 2 == 0:
				a[i][j] = z
			else:
				a[i][n - j - 1] = z
			z += 1
	a[n - 1][0] = z
	z += 1
	a[n - 2][0] = z
	z += 1
	a[n - 3][0] = z
	z += 1
	for j in range(1, n - 4):
		a[n - 3][j] = z
		z += 1
		a[n - 2][j] = z
		z += 1
		a[n - 1][j] = z
		z += 1
		if j % 2 == 1:
			(a[n - 3][j], a[n - 1][j]) = (a[n - 1][j], a[n - 3][j])
elif n % 2 == 0:
	for i in range(n - 3):
		for j in range(n):
			if i % 2 == 1:
				a[i][j] = z
			else:
				a[i][n - j - 1] = z
			z += 1
	for j in range(n - 4):
		a[n - 3][j] = z
		z += 1
		a[n - 2][j] = z
		z += 1
		a[n - 1][j] = z
		z += 1
		if j % 2 == 1:
			(a[n - 3][j], a[n - 1][j]) = (a[n - 1][j], a[n - 3][j])
if n >= 4:
	m = n ** 2
	a[n - 3][n - 4] = m - 6
	a[n - 3][n - 3] = m - 5
	a[n - 3][n - 2] = m - 10
	a[n - 3][n - 1] = m - 11
	a[n - 2][n - 4] = m - 8
	a[n - 2][n - 3] = m
	a[n - 2][n - 2] = m - 9
	a[n - 2][n - 1] = m - 2
	a[n - 1][n - 4] = m - 7
	a[n - 1][n - 3] = m - 4
	a[n - 1][n - 2] = m - 3
	a[n - 1][n - 1] = m - 1
	prt(a, n)


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
n = val()
l = [[0] * n for i in range(n)]
if n < 3:
	print(-1)
	exit()
curr = 0

def givecurr():
	global curr
	curr += 1
	return curr
up = [[5, 4, 1], [3, 2, 9], [8, 6, 7]]
down = [[7, 6, 8], [9, 2, 3], [1, 4, 5]]
totleft = n ** 2 - 9
i = n - 1
takeup = j = 0
while totleft:
	while i >= 0 and j >= 0 and (l[i][j] == 0):
		l[i][j] = givecurr()
		totleft -= 1
		i -= 1
	i += 1
	j += 1
	while j < n:
		l[i][j] = givecurr()
		totleft -= 1
		j += 1
	j = n - 1
	i += 1
	if not totleft:
		takeup = 1
		break
	while j >= 0 and l[i][j] == 0:
		l[i][j] = givecurr()
		totleft -= 1
		j -= 1
	j += 1
	i += 1
	while i < n:
		l[i][j] = givecurr()
		totleft -= 1
		i += 1
	i = n - 1
	j += 1
for i in range(3):
	for j in range(3):
		l[i + n - 3][j + n - 3] = curr + (up[i][j] if takeup else down[i][j])
for i in l:
	print(*i)


import sys
n = int(input())
if n <= 2:
	print(-1)
	sys.exit(0)
elif n == 3:
	board = [[4, 5, 8], [3, 2, 6], [1, 9, 7]]
else:
	board = [[0 for _ in range(n)] for _ in range(n)]
	curr = 1
	for i in range(1, n - 1):
		board[0][i] = curr
		curr += 1
	for i in range(n - 1):
		board[1][n - 2 - i] = curr
		curr += 1
	board[2][0] = curr
	curr += 1
	for i in range(2, n):
		board[i][n - 1] = curr
		curr += 1
	board[1][n - 1] = curr
	curr += 1
	board[0][n - 1] = curr
	curr += 1
	board[0][0] = n * n
	board[n - 1][0] = curr
	curr += 1
	for i in range(3, n - 1):
		board[i][0] = curr
		curr += 1
	for i in range(2, n):
		board[i][n - 2] = curr
		curr += 1
	bottom = True
	for i in range(n - 3, 0, -1):
		if bottom:
			for j in range(n - 1, 1, -1):
				board[j][i] = curr
				curr += 1
		else:
			for j in range(2, n):
				board[j][i] = curr
				curr += 1
		bottom = not bottom
for r in board:
	print(' '.join(map(str, r)))


n = int(input())
b = list([list([0, 6, 5]), list([1, 4, 3]), list([8, 2, 7])])
a = list(list())
if n < 3:
	print(-1)
else:
	for i in range(n):
		cur = list()
		for j in range(n):
			cur.append(0)
		a.append(cur.copy())
	val = 1
	for i in range(n - 1, 2, -1):
		if i % 2 == 0:
			for j in range(i + 1):
				a[i][j] = val
				val += 1
			for j in range(i - 1, -1, -1):
				a[j][i] = val
				val += 1
		else:
			for j in range(i + 1):
				a[j][i] = val
				val += 1
			for j in range(i - 1, -1, -1):
				a[i][j] = val
				val += 1
	for i in range(3):
		for j in range(3):
			a[i][j] = val + b[i][j]
	for i in range(n):
		for j in range(n):
			print(a[i][j], end=' ')
		print('')


ls = [[6, 3, 8], [1, 2, 7], [9, 4, 5]]
n = int(input())
if n <= 2:
	print(-1)
	exit()
ans = [[0 for i in range(n)] for j in range(n)]
for i in range(3):
	for j in range(3):
		ans[i][j] = ls[i][j] + n ** 2 - 9
(x, y) = (2, 0)
d = 'D'
for i in range(1, n ** 2 - 8)[::-1]:
	if d == 'D':
		x += 1
	if d == 'U':
		x -= 1
	if d == 'L':
		y -= 1
	if d == 'R':
		y += 1
	ans[x][y] = i
	if x == y:
		if d == 'D':
			d = 'L'
		elif d == 'R':
			d = 'U'
	elif x == 0:
		if d == 'U':
			d = 'R'
		elif d == 'R':
			d = 'D'
	elif y == 0:
		if d == 'L':
			d = 'D'
		elif d == 'D':
			d = 'R'
for row in ans:
	print(*row)


def solve(n):
	arr = [[0] * n for _ in range(n)]
	arr[0][1] = n * n
	arr[n - 1][n - 1] = n * n - 1
	arr[n - 1][1] = n * n - 2
	arr[0][n - 1] = n * n - (n + 1)
	cur = 1
	r = n - 2
	row_ = None
	for i in range(n):
		if arr[0][i] != 0:
			continue
		arr[0][i] = cur
		row_ = i
		cur += 1
		r -= 1
		if r == 0:
			break
	for col in range(1, n - 1):
		arr[col][row_] = cur
		cur += 1
		r = n - 1
		if col != n - 2:
			arr[col][n - 1] = cur
			cur += 1
			r -= 1
		for i in range(n):
			if arr[col][i] != 0:
				continue
			arr[col][i] = cur
			row_ = i
			cur += 1
			r -= 1
			if r == 0:
				break
	cur += 1
	r = n - 2
	for i in range(n):
		if arr[n - 1][i] != 0:
			continue
		arr[n - 1][i] = cur
		cur += 1
		r -= 1
		if r == 0:
			break
	return arr
n = int(input())
if n < 3:
	print(-1)
else:
	arr = solve(n)
	for a in arr:
		print(' '.join([str(x) for x in a]))


def main():
	L = [[0 for _ in range(501)] for _ in range(501)]
	n = int(input())
	if n <= 2:
		print(-1)
		return
	lf = 1
	rt = n
	id = n
	cur = 1
	direct = 1
	cnt = 0
	if n % 2 == 1:
		direct = -1
		cur = n
	while id > 0:
		if n == 3:
			break
		cnt += 1
		L[id][cur] = cnt
		if cur + direct >= lf and cur + direct <= rt:
			cur += direct
		else:
			id -= 1
			direct *= -1
		if id == 3:
			lf = 4
	L[1][1] = 1 + cnt
	L[1][2] = 7 + cnt
	L[1][3] = 9 + cnt
	L[2][1] = 3 + cnt
	L[2][2] = 2 + cnt
	L[2][3] = 5 + cnt
	L[3][1] = 4 + cnt
	L[3][2] = 8 + cnt
	L[3][3] = 6 + cnt
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			print(L[i][j], end=' ')
		print()
main()


def main():
	n = int(input())
	if n < 3:
		print(-1)
		return
	ans = [[0] * n for _ in range(n)]
	st = n * n - 9
	ans[0][0:3] = [st + 6, st + 5, st + 8]
	ans[1][0:3] = [st + 7, st + 3, st + 4]
	ans[2][0:3] = [st + 1, st + 2, st + 9]
	cur = 1
	k = 0
	while n - k > 3:
		if (n - k) % 2:
			for j in range(n - k - 1):
				ans[n - k - 1][j] = cur
				cur += 1
			for i in reversed(range(n - k)):
				ans[i][n - k - 1] = cur
				cur += 1
		else:
			for i in range(n - k):
				ans[i][n - k - 1] = cur
				cur += 1
			for j in reversed(range(n - k - 1)):
				ans[n - k - 1][j] = cur
				cur += 1
		k += 1
	for row in ans:
		print(*row)
main()


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	if N <= 2:
		print(-1)
		exit()
	ans = [[0] * N for _ in range(N)]
	for h in range(N - 1):
		if h % 2 == 0:
			for w in range(N):
				ans[h][w] = h * N + w
		else:
			for w in range(N):
				ans[h][N - w - 1] = h * N + w
	if N % 2 == 0:
		(ans[N - 2][N - 2], ans[N - 2][N - 1]) = (ans[N - 2][N - 1], ans[N - 2][N - 2])
	else:
		(ans[N - 2][N - 2], ans[N - 2][0]) = (ans[N - 2][0], ans[N - 2][N - 2])
	ans[N - 1][N - 1] = N * N - N
	for w in range(N - 1):
		ans[N - 1][N - w - 2] = N * N - N + w
	ans[0][0] = N * N - 1
	ans[N - 1][N - 2] = N * N
	for h in range(N):
		print(*ans[h])
main()


n = int(input())
if n <= 2:
	print(-1)
else:
	out = [[0] * n for i in range(n)]
	out[0][0] = 9
	out[0][1] = 3
	out[0][2] = 1
	out[1][0] = 7
	out[1][1] = 8
	out[1][2] = 5
	out[2][0] = 6
	out[2][1] = 2
	out[2][2] = 4
	flip = True
	for i in range(3, n):
		if flip:
			for j in range(i + 1):
				out[j][i] = i * i + j + 1
			for j in range(i):
				out[i][j] = (i + 1) * (i + 1) - j
		else:
			for j in range(i + 1):
				out[i][j] = i * i + j + 1
			for j in range(i):
				out[j][i] = (i + 1) * (i + 1) - j
	for l in out:
		print(' '.join(map(lambda x: str(n * n + 1 - x), l)))


n = input()
n = int(n)
if n <= 2:
	print(-1)
elif n % 2 == 0:
	for row in range(n):
		if row == 0:
			for i in range(n):
				if i == 0:
					print(i + 1, end=' ')
				elif i == n - 1:
					print(i + 1)
				else:
					print(i + 1, end=' ')
		elif row == n - 1:
			for i in range(n):
				if i == n - 1:
					print(n * n - 1)
				else:
					print(n + (n - 1) * (n - 2) + (n - 3) - i + 2, end=' ')
		elif row == n - 2:
			for i in range(n):
				if i == 0:
					print(n * n - n + 2 + row, end=' ')
				elif i < n - 1:
					print(n + (n - 1) * (row - 1) + i, end=' ')
				else:
					print(n + (n - 1) * (row - 1) + n - 1)
		elif row % 2 == 1:
			for i in range(n):
				if i == 0:
					print(n * n - n + 2 + row - 1, end=' ')
				elif i < n - 1:
					print(n + (n - 1) * (row - 1) + n - i, end=' ')
				else:
					print(n + (n - 1) * (row - 1) + 1)
		elif row % 2 == 0:
			for i in range(n):
				if i == 0:
					print(n * n - n + 2 + row - 1, end=' ')
				elif i < n - 1:
					print(n + (n - 1) * (row - 1) + i, end=' ')
				else:
					print(n + (n - 1) * (row - 1) + n - 1)
elif n % 2 == 1:
	for row in range(n):
		if row == 0:
			for i in range(n):
				if i == 0:
					print(i + 1, end=' ')
				elif i == n - 1:
					print(n * n - n + row + 1)
				else:
					print(i + 1, end=' ')
		elif row == n - 1:
			for i in range(n):
				if i == 0:
					print(n * n - 1, end=' ')
				elif i == n - 1:
					print((n - 1) * (n - 1) + i)
				else:
					print((n - 1) * (n - 1) + i, end=' ')
		elif row == n - 2:
			for i in range(n):
				if i == 0:
					print((n - 1) * row + n - i - 1, end=' ')
				elif i < n - 1:
					print((n - 1) * row + n - i - 1, end=' ')
				else:
					print(n * n)
		elif row % 2 == 1:
			for i in range(n):
				if i == 0:
					print((n - 1) * row + n - i - 1, end=' ')
				elif i < n - 1:
					print((n - 1) * row + n - i - 1, end=' ')
				else:
					print(n * n - n + row + 1)
		elif row % 2 == 0:
			for i in range(n):
				if i == 0:
					print((n - 1) * row + i + 1, end=' ')
				elif i < n - 1:
					print((n - 1) * row + i + 1, end=' ')
				else:
					print(n * n - n + row + 1)


import sys
input = sys.stdin.buffer.readline
N = int(input())
if N < 3:
	print(-1)
	exit(0)
board = [[0 for j in range(N)] for i in range(N)]
base = [[7, 4, 8], [9, 2, 3], [1, 5, 6]]
i = 3 + (N - 2) // 2
j = (N - 1) // 2 + 2
val = N * N - 8
for x in range(-3, 0):
	for y in range(-3, 0):
		board[i + x][j + y] = N * N - 9 + base[x + 3][y + 3]
for n in range(4, N + 1):
	if n & 1:
		for inc in range(n):
			val -= 1
			i += 1
			board[i][j] = val
		for inc in range(n - 1):
			val -= 1
			j += 1
			board[i][j] = val
		i += 1
		j += 1
	else:
		for inc in range(n):
			val -= 1
			i -= 1
			board[i][j] = val
		for inc in range(n - 1):
			val -= 1
			j -= 1
			board[i][j] = val
		j -= 1
		i -= 1
for b in board:
	print(*b)