Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Chef has a matrix $A$ with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$); an element in row $i$ and column $j$ is denoted by $A_{i, j}$. He is going to play a game on this matrix with Chefina. In the game, Chef lists the elements of the matrix row by row in an alternating pattern, starting from the top left corner ― he writes down the first row from left to right, the second row from right to left, and so on. Chefina also lists the elements of the matrix row by row, but she starts from the top right corner and writes down the first row from right to left, the second row from left to right, and so on.

Chefina gets impressed if the sequences written by Chef and Chefina turn out to be the same. Chef can rearrange the matrix in any way he chooses in order to impress Chefina. In the rearranged matrix, the number of occurrences of each integer must be the same as in the original matrix.

For example, if the initial matrix is

1 1
1 2

then there are four possible rearrangements:

1 1     1 1     1 2     2 1
1 2     2 1     1 1     1 1

Find one way in which Chef can rearrange the matrix to impress Chefina or determine that it is impossible.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$. 
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains $M$ space-separated integers $A_{i, 1}, A_{i, 2}, \ldots, A_{i, M}$.

------  Output ------
For each test case:
If it is impossible to rearrange the matrix in such a way that Chefina gets impressed, print a single line containing the integer $-1$.
Otherwise, print $N$ lines describing your rearranged matrix. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines should contain $M$ space-separated integers ― the elements in the $i$-th row of the rearranged matrix. This matrix must have the same number of occurrences of each integer as the original matrix.

If there is more than one possible answer, you may find any one.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N, M ≤ 300$
$1 ≤ A_{i, j} ≤ 10^{5}$ for each valid $i, j$
the sum of $N \cdot M$ over all test cases does not exceed $5 \cdot 10^{5}$

----- Sample Input 1 ------ 
3

1 2

1 1

2 2

1 1

2 1

3 3

1 2 3

6 5 4

7 8 9
----- Sample Output 1 ------ 
1 1

-1

-1
----- explanation 1 ------ 
Example case 1: The sequence printed by Chef is always $[1, 1]$ and the sequence printed by Chefina is also always $[1, 1]$, so Chef does not need to change the matrix and Chefina will be impressed.

Difficulty: HARD
Tags: String algorithms

Starter code:

Solutions:
from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().rstrip().split())
	mat = []
	for i in range(n):
		a = list(map(int, input().rstrip().split()))
		if not i & 1:
			mat.append(a)
		else:
			mat.append(a)
	d = defaultdict(lambda : 0)
	for i in mat:
		for j in i:
			d[j] += 1
	mm = [[0] * m for i in range(n)]
	flag = 0
	for i in range(n):
		for j in range(0, m // 2):
			f = 0
			for k in d:
				if d[k] >= 2:
					cur = k
					d[k] -= 2
					f = 1
					break
			if f == 0 and flag != 1:
				print(-1)
				flag = 1
				break
			mm[i][j] = cur
			mm[i][-1 - j] = cur
	if flag != 1:
		if m % 2 == 1:
			for i in range(n):
				for j in d:
					if d[j] >= 1:
						cur = j
						d[j] -= 1
						break
				mm[i][m // 2] = cur
		for i in mm:
			for j in i:
				print(j, end=' ')
			print()


from sys import stdin
input = stdin.readline

def answer():
	d = dict()
	for i in range(n):
		for j in range(m):
			d[a[i][j]] = d.get(a[i][j], 0) + 1
	ans = [[0 for i in range(m)] for j in range(n)]
	odds = []
	(i, j) = (0, 0)
	for x in d.keys():
		if m & 1 == 0 and d[x] & 1:
			print(-1)
			return
		count = d[x]
		while count > 1:
			if m & 1 and j == m // 2:
				break
			ans[i][j] = ans[i][m - j - 1] = x
			i += 1
			if i == n:
				j += 1
				i = 0
			count -= 2
		odds += [x for i in range(count)]
	if len(odds) > n:
		print(-1)
		return
	if m & 1:
		for i in range(n):
			ans[i][m // 2] = odds[i]
	for x in ans:
		print(*x)
for T in range(int(input())):
	(n, m) = map(int, input().split())
	a = [list(map(int, input().split())) for i in range(n)]
	answer()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	matrix = []
	for i in range(n):
		li = list(map(int, input().split()))
		matrix.append(li)
	d = {}
	l = []
	for i in range(n):
		for j in range(m):
			if d.get(matrix[i][j]) == None:
				d[matrix[i][j]] = 1
				l.append(matrix[i][j])
			else:
				d[matrix[i][j]] += 1
	(odd, even) = (0, 0)
	for (x, y) in d.items():
		if y % 2:
			odd += 1
		else:
			even += 1
	if m % 2 == 0:
		if odd > 0:
			print(-1)
		else:
			index = 0
			for i in range(n):
				for j in range(m // 2):
					if d[l[index]] == 0:
						index += 1
					(matrix[i][j], matrix[i][m - j - 1]) = (l[index], l[index])
					d[l[index]] -= 2
			for i in range(n):
				for j in range(m):
					print(matrix[i][j], end=' ')
				print()
	elif odd > n:
		print(-1)
	else:
		mid = m // 2
		li = []
		index = 0
		for i in range(n):
			for j in range(m // 2):
				if d[l[index]] == 0:
					index += 1
				while d[l[index]] == 1:
					li.append(l[index])
					index += 1
				(matrix[i][j], matrix[i][m - j - 1]) = (l[index], l[index])
				d[l[index]] -= 2
		for i in range(n):
			if index < len(l) and d[l[index]] == 0:
				index += 1
			if index < len(l):
				matrix[i][mid] = l[index]
				d[l[index]] -= 1
			else:
				matrix[i][mid] = li.pop()
		for i in range(n):
			for j in range(m):
				print(matrix[i][j], end=' ')
			print()


t = int(input())
for _ in range(t):
	(r, c) = map(int, input().split())
	arr = []
	for i in range(r):
		arr.append(list(map(int, input().split())))
	h = {}
	for i in range(r):
		for j in range(c):
			if h.get(arr[i][j]) != None:
				h[arr[i][j]] += 1
			else:
				h[arr[i][j]] = 1
	temp = True
	if c % 2 == 0:
		k = []
		for i in h.keys():
			k.append(i)
			if h[i] % 2 != 0:
				temp = False
				break
		if temp == False:
			print(-1)
		else:
			q = 0
			for i in range(r):
				for j in range(c // 2):
					if h[k[q]] == 0:
						q += 1
					arr[i][j] = k[q]
					arr[i][c - j - 1] = k[q]
					h[k[q]] -= 2
			for i in range(r):
				for j in range(c):
					print(arr[i][j], end=' ')
				print()
	else:
		odd = 0
		k = []
		for i in h.keys():
			k.append(i)
			if h[i] % 2:
				odd += 1
		if odd > r:
			print(-1)
		else:
			q = 0
			v = []
			for i in range(r):
				for j in range(c // 2):
					if h[k[q]] == 0:
						q += 1
					while h[k[q]] == 1:
						v.append(k[q])
						q += 1
					arr[i][j] = k[q]
					arr[i][c - j - 1] = k[q]
					h[k[q]] -= 2
			for i in range(r):
				if q < len(k) and h[k[q]] == 0:
					q += 1
				if q < len(k):
					arr[i][c // 2] = k[q]
					h[k[q]] -= 1
				else:
					arr[i][c // 2] = v[-1]
					v.pop()
			for i in range(r):
				for j in range(c):
					print(arr[i][j], end=' ')
				print()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	h = {}
	for i in range(n):
		for i in map(int, input().split()):
			h[i] = h.get(i, 0) + 1
	if m % 2 == 0:
		ok = True
		for i in h:
			if h[i] % 2:
				ok = False
				print(-1)
				break
		if ok:
			rows = 0
			while rows != n:
				cnt = 0
				r = []
				for i in h:
					while h[i] != 0 and cnt != m:
						r.append(i)
						h[i] -= 2
						cnt += 2
				rv = r[::-1]
				row = r + rv
				rows += 1
				print(*row)
	else:
		ok = True
		c = 0
		for i in h:
			if h[i] % 2:
				c += 1
			if c > n:
				ok = False
				print(-1)
				break
		if ok:
			rows = 0
			while rows != n:
				cnt = 0
				r = []
				mid = []
				for i in h:
					while cnt != m // 2 and h[i] != 0 and (h[i] != 1):
						r.append(i)
						h[i] -= 2
						cnt += 1
				k = True
				for i in h:
					if h[i] % 2:
						mid.append(i)
						k = False
						h[i] -= 1
						break
				if k:
					for i in h:
						if h[i] != 0:
							mid.append(i)
							h[i] -= 1
							break
				rows += 1
				rv = r[::-1]
				row = r + mid + rv
				print(*row)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = []
	s = set()
	len_s = 0
	len_l = 0
	for i in range(n):
		d = list(map(int, input().split()))
		for j in range(m):
			if d[j] not in s:
				s.add(d[j])
				len_s += 1
			else:
				s.remove(d[j])
				l.append(d[j])
				len_s -= 1
				len_l += 1
	n1 = (n - len_s) % 2
	if m % 2 == 0 and len_s != 0 or len_s > n or (len_s != 0 and n1 == 1):
		print(-1)
	else:
		s = list(s)
		if len_s != 0 or m % 2 == 1:
			n1 = (n - len_s) // 2
			l1 = l[:n1]
			l = l[n1:]
			s = s + l1 * 2
		a = 0
		b = 0
		if m % 2 == 0:
			for i in range(n):
				rs = str(l[a]) + ' ' + str(l[a])
				a += 1
				for j in range(1, m // 2):
					rs = str(l[a]) + ' ' + rs + ' ' + str(l[a])
					a += 1
				print(rs)
		else:
			for i in range(n):
				rs = str(s[b])
				b += 1
				for j in range(m // 2):
					rs = str(l[a]) + ' ' + rs + ' ' + str(l[a])
					a += 1
				print(rs)


from collections import defaultdict

def fn(m):
	d = defaultdict(lambda : 0)
	for i in m:
		for j in i:
			d[j] += 1
	fm = []
	mm = [[0] * len(m[0]) for i in range(len(m))]
	for i in range(len(m)):
		for j in range(0, len(m[0]) // 2):
			f = 0
			for k in d:
				if d[k] >= 2:
					cur = k
					d[k] -= 2
					f = 1
					break
			if f == 0:
				print(-1)
				return
			mm[i][j] = cur
			mm[i][-1 - j] = cur
	if len(m[0]) % 2 == 1:
		for i in range(len(m)):
			for j in d:
				if d[j] >= 1:
					cur = j
					d[j] -= 1
					break
			mm[i][len(m[0]) // 2] = cur
	for i in mm:
		for j in i:
			print(j, end=' ')
		print()
t = int(input())
for x in range(t):
	(n, m) = map(int, input().rstrip().split())
	cm = []
	for i in range(n):
		a = list(map(int, input().rstrip().split()))
		if i % 2 == 0:
			cm.append(a)
		else:
			cm.append(a)
	fn(cm)


from collections import Counter, deque
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	matrix = []
	for _ in range(n):
		matrix += map(int, input().split())
	occurrences = Counter(matrix)
	odd = []
	even = []
	row = deque()
	for (num, occ) in occurrences.items():
		if occ % 2:
			odd.append(num)
		else:
			even.append(num)
	if m % 2 and len(odd) > n or (not m % 2 and len(odd)):
		print(-1)
	else:
		for _ in range(n):
			if m % 2:
				if odd:
					i = odd[0]
					odd.remove(i)
					if occurrences[i] == 1:
						del occurrences[i]
					else:
						occurrences[i] -= 1
						even.append(i)
				else:
					i = even[0]
					odd.append(i)
					even.remove(i)
					occurrences[i] -= 1
				row.append(i)
			for _ in range(m // 2):
				if even:
					i = even[0]
					if occurrences[i] == 2:
						even.remove(i)
						del occurrences[i]
					else:
						occurrences[i] -= 2
				else:
					j = 0
					while occurrences[odd[j]] < 2:
						j += 1
					i = odd[j]
					occurrences[i] -= 2
				row.append(i)
				row.appendleft(i)
			print(*row)
			row.clear()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	dic = {}
	for i in range(n):
		t = list(map(int, input().split()))
		for j in t:
			if j in dic:
				dic[j] += 1
			else:
				dic[j] = 1
	odd_cnt = {}
	key = list(dic.keys())
	for i in key:
		if dic[i] % 2 == 1:
			odd_cnt[i] = dic[i]
			t = dic.pop(i)
	if m % 2 == 0 and odd_cnt:
		print(-1)
		continue
	elif len(odd_cnt) > n:
		print(-1)
		continue
	mat = []
	k = 0
	num = list(dic.keys())
	mat = [[-1 for i in range(m)] for j in range(n)]
	if m % 2 == 1:
		for i in range(n):
			t = mat[i]
			if not odd_cnt:
				t[m // 2] = num[k]
				odd_cnt[num[k]] = dic[num[k]] - 1
				temp = dic.pop(num[k])
				k += 1
			else:
				temp = list(odd_cnt.keys())[0]
				t[m // 2] = temp
				odd_cnt[temp] -= 1
				if odd_cnt[temp] != 0:
					dic[temp] = odd_cnt[temp]
					num.append(temp)
				temp = odd_cnt.pop(temp)
	k = 0
	num = list(dic.keys())
	for i in range(n):
		t = mat[i]
		for j in range(m // 2):
			dic[num[k]] -= 2
			(t[j], t[m - j - 1]) = (num[k], num[k])
			if dic[num[k]] == 0:
				temp = dic.pop(num[k])
				k += 1
	for i in range(n):
		for j in range(m):
			print(mat[i][j], end=' ')
		print('')


from collections import deque
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(arr, data, ctr) = (list(), dict(), 0)
	for i in range(n):
		arr.append(list(map(int, input().split())))
		for j in range(m):
			if arr[i][j] in data:
				data[arr[i][j]] += 1
			else:
				data[arr[i][j]] = 1
	for ele in data:
		if data[ele] % 2 != 0:
			ctr += 1
	if m % 2 == 0:
		if ctr:
			print(-1)
			continue
	elif ctr > n:
		print(-1)
		continue
	(odd, even) = (deque([]), deque([]))
	for ele in data:
		if data[ele] % 2 == 0:
			even.append(ele)
		else:
			odd.append(ele)
	for i in range(n):
		ans = deque([])
		if m % 2 != 0:
			if odd:
				ans.append(odd[0])
				data[odd[0]] -= 1
				pop = odd.popleft()
				if data[pop] > 0:
					even.append(pop)
			else:
				ans.append(even[0])
				data[even[0]] -= 1
				pop = even.popleft()
				if data[pop] > 0:
					odd.append(pop)
		for j in range(m // 2):
			if even:
				pop = even[0]
				ans.appendleft(pop)
				ans.append(pop)
				data[pop] -= 2
				if data[pop] == 0:
					even.popleft()
			else:
				pop = odd[0]
				ans.appendleft(pop)
				ans.append(pop)
				data[pop] -= 2
		for i in ans:
			print(i, end=' ')
		print()


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = []
	n = []
	for j in range(a):
		o = list(map(int, input().split()))
		l.append(o)
	f = {}
	for j in range(a):
		for k in range(b):
			if l[j][k] in f:
				f[l[j][k]] += 1
			else:
				f[l[j][k]] = 1
				n.append(l[j][k])
	if b % 2 == 0:
		p = 0
		for e in f:
			if f[e] % 2 == 1:
				p = 1
				break
		if p == 1:
			print(-1)
		else:
			s = 0
			for j in range(a):
				for k in range(b // 2):
					if f[n[s]] == 0:
						s += 1
					(l[j][k], l[j][b - k - 1]) = (n[s], n[s])
					f[n[s]] -= 2
			for j in l:
				for k in j:
					print(k, end=' ')
				print('')
	else:
		c = 0
		for v in f:
			c += f[v] // 2 * 2
		if c < a * b - a:
			print(-1)
		else:
			s = 0
			for j in range(a):
				for k in range(b // 2):
					while f[n[s]] <= 1:
						s += 1
					(l[j][k], l[j][b - k - 1]) = (n[s], n[s])
					f[n[s]] -= 2
			(j, k) = (0, b // 2)
			for s in f:
				while f[s] > 0:
					l[j][k] = s
					j += 1
					f[s] -= 1
			for j in l:
				for k in j:
					print(k, end=' ')
				print('')


from collections import defaultdict
t = int(input())
for test in range(t):
	(m, n) = map(int, input().split())
	a = []
	for j in range(m):
		a.append(list(map(int, input().split())))
	count = defaultdict(int)
	for i in range(m):
		for j in range(n):
			count[a[i][j]] += 1
	(A, B) = ([], [])
	(P, Q) = ([], [])
	for k in count.keys():
		if count[k] % 2 == 0:
			A.append(k)
		else:
			B.append(k)
	odd = len(B)
	if n % 2 == 0 and odd != 0 or (n % 2 == 1 and (m < odd or (m - odd) % 2 == 1)):
		print(-1)
	else:
		ans = []
		for j in A:
			P += [j] * count[j]
		for j in B:
			Q.append(j)
			P += [j] * (count[j] - 1)
		if n % 2 == 1:
			while len(Q) != m:
				Q += P[:2]
				P = P[2:]
		if n % 2 == 0:
			for i in range(m):
				X = []
				for j in range(n // 2):
					X.append(P[0])
					P = P[2:]
				X += X[::-1]
				x = ' '.join(map(str, X))
				ans += [x]
		else:
			for i in range(m):
				X = []
				for j in range(n // 2):
					X.append(P[0])
					P = P[2:]
				X += [Q[i]] + X[::-1]
				x = ' '.join(map(str, X))
				ans += [x]
		for i in ans:
			print(i)


from collections import deque

def buildMatrix(matrix, R, C, unique: list, double: deque):
	for i in range(R):
		n_row = []
		for _ in range(C // 2):
			p = len(n_row) // 2
			n_row[p:p] = [double.popleft()] * 2
		if C % 2 == 1:
			if not unique:
				unique.extend([double.pop()] * 2)
			p = len(n_row) // 2
			n_row[p:p] = [unique.pop(0)]
		matrix[i] = n_row
	return matrix

def solve(matrix: list) -> list:
	R = len(matrix)
	C = len(matrix[0])
	unique = set()
	double = deque()
	for r in range(R):
		for c in range(C):
			if matrix[r][c] in unique:
				unique.remove(matrix[r][c])
				double.append(matrix[r][c])
			else:
				unique.add(matrix[r][c])
	if C % 2 == 0:
		if unique:
			raise Exception()
	return buildMatrix(matrix, R, C, list(unique), double)
ans = []
for _ in range(int(input())):
	try:
		(N, M) = map(int, input().split())
		matrix = []
		needProcessing = False
		for _ in range(N):
			Ms = list(map(int, input().split()))
			matrix.append(Ms)
			if not needProcessing and Ms != reversed(Ms):
				needProcessing = True
		if needProcessing:
			matrix = solve(matrix)
		for r in matrix:
			ans.append(' '.join(map(str, r)))
	except:
		ans.append('-1')
print(*ans, sep='\n')


T = int(input())
for _ in range(T):
	(n, m) = list(map(int, input().split()))
	A = []
	hashmap = {}
	for i in range(n):
		temp = list(map(int, input().split()))
		A.append(temp)
		for j in temp:
			if j in hashmap:
				hashmap[j] += 1
			else:
				hashmap[j] = 1
	uniq = 0
	u = []
	for i in hashmap:
		if hashmap[i] % 2 != 0:
			uniq += 1
			u.append(i)
			hashmap[i] -= 1
	k = m % 2
	no_of_uni = k * n
	if no_of_uni < uniq or abs(no_of_uni - uniq) % 2 != 0:
		print(-1)
		continue
	mid = m // 2
	val = m // 2
	if m % 2 == 0:
		mid = -1
		val = m // 2 + 1
	t = 0
	for key in hashmap:
		while hashmap[key]:
			if len(u) == no_of_uni:
				break
			u.append(key)
			hashmap[key] -= 1
		if len(u) == no_of_uni:
			break
	(i, j) = (0, 0)
	for key in hashmap:
		while hashmap[key]:
			A[i][j] = key
			A[i][m - j - 1] = key
			j += 1
			if j == m // 2:
				j = 0
				i += 1
			hashmap[key] -= 2
	if mid != -1:
		for i in range(n):
			A[i][mid] = u[t]
			t += 1
	for i in A:
		for j in range(m):
			if j == m - 1:
				print(i[j])
			else:
				print(i[j], end=' ')


for T in range(int(input())):
	(n, m) = list(map(int, input().split()))
	arr = []
	flag = False
	for i in range(n):
		lis = input()
		if lis != lis[::-1]:
			flag = True
		arr.append(list(lis.split()))
	if flag == False:
		for i in range(n):
			print(' '.join(arr[i]))
		continue
	d = []
	s = set()
	count1 = 0
	count2 = 0
	for i in range(n):
		for j in range(m):
			if not arr[i][j] in s:
				s.add(arr[i][j])
			else:
				d.append(arr[i][j])
				s.remove(arr[i][j])
				count2 += 2
	s = list(s)
	count1 = len(s)
	if m % 2 == 0 and count1 > 0 or (m % 2 == 1 and n - count1 < 0):
		print(-1)
	elif m % 2 == 0:
		k = 0
		for i in range(n):
			ans = ''
			for j in range(m // 2):
				if ans == '':
					ans = d[k] + ' ' + d[k]
				else:
					ans = d[k] + ' ' + ans + ' ' + d[k]
				k += 1
			print(ans)
	else:
		k = 0
		if n - count1 > 0:
			diff = (n - count1) // 2
			k += diff
			s.extend(d[:k] + d[:k])
		for i in range(n):
			p = s.pop()
			for j in range(m // 2):
				p = d[k] + ' ' + p + ' ' + d[k]
				k += 1
			print(p)


from collections import Counter
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	a = []
	for i in range(n):
		ai = [int(z) for z in input().split()]
		a.extend(ai)
	b = Counter(a)
	(m_even, impossible, odds) = (False, False, 0)
	evenvalues = []
	if m % 2 == 0:
		m_even = True
	else:
		oddvalues = []
	for k in b:
		if b[k] % 2 == 1:
			if m_even:
				impossible = True
				break
			else:
				odds += 1
				if odds > n:
					impossible = True
					break
				oddvalues.append(k)
		x = b[k] // 2
		la = [k] * x
		evenvalues.extend(la)
	if impossible:
		print('-1')
	elif m_even:
		x = m // 2
		for i in range(n):
			sp = i * x
			ep = (i + 1) * x
			lf = evenvalues[sp:ep]
			lr = lf[::-1]
			lf.extend(lr)
			print(*lf)
	else:
		x = m // 2
		y = n * x
		middles = evenvalues[y:]
		oddvalues.extend(middles)
		oddvalues.extend(middles)
		for i in range(n):
			sp = i * x
			ep = (i + 1) * x
			lf = evenvalues[sp:ep]
			lr = lf[::-1]
			lf.append(oddvalues[i])
			lf.extend(lr)
			print(*lf)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [0] * n
	for i in range(n):
		l[i] = list(map(int, input().split()))
	d = {}
	ele = []
	for i in range(n):
		for j in range(m):
			if l[i][j] not in d:
				d[l[i][j]] = 1
				ele.append(l[i][j])
			else:
				d[l[i][j]] += 1
	if m % 2 == 0:
		temp = 0
		for e in d:
			if d[e] % 2 != 0:
				temp = 1
				break
		if temp == 1:
			print(-1)
			continue
		k = 0
		for i in range(n):
			for j in range(m // 2):
				if d[ele[k]] == 0:
					k += 1
				d[ele[k]] -= 2
				(l[i][j], l[i][m - 1 - j]) = (ele[k], ele[k])
	else:
		c = 0
		for e in d:
			c += d[e] // 2 * 2
		if c < n * m - n:
			print(-1)
			continue
		k = 0
		for i in range(n):
			for j in range(m // 2):
				while d[ele[k]] <= 1:
					k += 1
				d[ele[k]] -= 2
				(l[i][j], l[i][m - 1 - j]) = (ele[k], ele[k])
		i = 0
		j = m // 2
		for e in d:
			while d[e] > 0:
				l[i][j] = e
				i += 1
				d[e] -= 1
	for e in l:
		print(*e)


def isvalid(freq):
	for i in freq:
		if freq[i] % 2:
			return 0
	return 1

def isvalid1(freq):
	count = 0
	for i in freq:
		if freq[i] % 2:
			count += 1
		if count > n:
			return 0
	return 1
t = int(input())
for you in range(t):
	freq = dict()
	l = input().split()
	n = int(l[0])
	m = int(l[1])
	lfi = []
	for i in range(n):
		s = input().split()
		lfi.append(s)
	for i in range(n):
		for j in range(m):
			if int(lfi[i][j]) in freq:
				freq[int(lfi[i][j])] += 1
				continue
			freq[int(lfi[i][j])] = 1
	mat = [[0 for i in range(m)] for j in range(n)]
	if m % 2 == 0:
		if isvalid(freq) == 0:
			print(-1)
			continue
		lfi = []
		for i in freq:
			if freq[i] != 0:
				lfi.append([i, freq[i]])
		for j in range(m):
			for i in range(n):
				if lfi == []:
					break
				mat[i][j] = lfi[0][0]
				mat[i][m - 1 - j] = lfi[0][0]
				lfi[0][1] -= 2
				if lfi[0][1] == 0:
					lfi.pop(0)
			if lfi == []:
				break
		for i in range(n):
			for j in range(m):
				print(mat[i][j], end=' ')
			print()
	else:
		if isvalid1(freq) == 0:
			print(-1)
			continue
		lfodd = []
		lfeven = []
		for i in freq:
			if freq[i] != 0:
				if freq[i] % 2:
					lfodd.append(i)
					if freq[i] > 1:
						lfeven.append([i, freq[i] - 1])
				else:
					lfeven.append([i, freq[i]])
		for i in range(n - 1, -1, -1):
			if lfodd == []:
				break
			mat[i][(m - 1) // 2] = lfodd[0]
			lfodd.pop(0)
		for j in range(m):
			for i in range(n):
				if lfeven == []:
					break
				mat[i][j] = lfeven[0][0]
				mat[i][m - 1 - j] = lfeven[0][0]
				if j == m - 1 - j:
					lfeven[0][1] -= 1
				else:
					lfeven[0][1] -= 2
				if lfeven[0][1] == 0:
					lfeven.pop(0)
			if lfeven == []:
				break
		for i in range(n):
			for j in range(m):
				print(mat[i][j], end=' ')
			print()


from itertools import *
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l += [int(i) for i in input().split()]
	l.sort()
	v = [(int(i), len(list(j))) for (i, j) in groupby(l)]
	en = []
	on = []
	for (i, j) in v:
		if j % 2 != 0:
			en += [i] * ((j - 1) // 2)
			on += [i]
		else:
			en += [i] * (j // 2)
	if m % 2 == 0 and len(on) != 0 or (m % 2 == 1 and len(on) > n):
		print(-1)
	elif m % 2 == 0:
		for i in range(n):
			g = en[i * (m // 2):(i + 1) * (m // 2)]
			g = g + g[-1::-1]
			print(' '.join((str(i) for i in g)))
	else:
		if len(on) < n:
			z = n - len(on)
			on += en[:z // 2] * 2
			en = en[z // 2:]
		for i in range(n):
			g = en[i * (m // 2):(i + 1) * (m // 2)]
			g = g + [on[i]] + g[-1::-1]
			print(' '.join((str(i) for i in g)))


from collections import Counter
for test_case in range(int(input())):
	(N, M) = map(int, input().split())
	matrix = []
	for i in range(N):
		matrix += list(map(int, input().split()))
	fre = Counter(matrix)
	even = {}
	odd = {}
	for x in fre:
		if fre[x] % 2 == 0:
			even[x] = fre[x]
		else:
			odd[x] = fre[x]
	len_odd = len(odd)
	if M % 2 == 0:
		if len_odd != 0:
			print(-1)
			continue
	elif len_odd > N:
		print(-1)
		continue
	matrix = []
	for j in range(N):
		matrix.append([-1] * M)
	ind = 0
	for item in odd:
		matrix[ind][M // 2] = item
		ind += 1
		value = odd[item] - 1
		if value > 0:
			even[item] = value
	high = M // 2
	i = j = 0
	for item in even:
		for c in range(even[item] // 2):
			if i == N or M == 1:
				matrix[ind][M // 2] = matrix[ind + 1][M // 2] = item
				ind += 2
				continue
			matrix[i][j] = matrix[i][M - 1 - j] = item
			j = j + 1
			if j == high:
				j = 0
				i += 1
	for item in matrix:
		print(*item)


def cal():
	matrix = [[-1 for _ in range(c)] for _ in range(r)]
	if c % 2 == 0:
		for j in m:
			if m[j] % 2 != 0:
				return -1
		(row, col) = (0, 0)
		for key in m:
			while m[key] > 0:
				matrix[row][col] = key
				matrix[row][c - col - 1] = key
				m[key] -= 2
				col += 1
				if col == c // 2:
					row += 1
					col = 0
	else:
		odd = {}
		even = {}
		for i in m:
			if m[i] % 2 == 0:
				even[i] = m[i]
			else:
				odd[i] = m[i]
		if len(odd) > r:
			return -1
		(row, col) = (0, 0)
		f = 0
		for i in odd:
			matrix[row][c // 2] = i
			odd[i] -= 1
			even[i] = odd[i]
			row += 1
			if row == r:
				f = 1
				break
		if f == 0:
			row = len(odd)
			for key in even:
				while even[key] > 0 and row < r:
					matrix[row][c // 2] = key
					even[key] -= 1
					row += 1
					if row == r:
						break
		(row, col) = (0, 0)
		for key in even:
			while even[key] > 0 and row < r:
				matrix[row][col] = key
				matrix[row][c - col - 1] = key
				even[key] -= 2
				col += 1
				if col == c // 2:
					row += 1
					col = 0
	return matrix
for _ in range(int(input())):
	(r, c) = map(int, input().split())
	l = []
	for i in range(r):
		l.append(list(map(int, input().split())))
	m = {}
	for temp in l:
		for j in temp:
			if j in m:
				m[j] += 1
			else:
				m[j] = 1
	t = cal()
	if t == -1:
		print(-1)
	else:
		for k in t:
			for h in k:
				print(h, end=' ')
		print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		k = list(map(int, input().split()))
		a += k
	freq = {}
	for i in a:
		if i not in freq.keys():
			freq[i] = 1
		else:
			freq[i] += 1
	even_frq = []
	odd_frq = []
	for (key, value) in zip(freq.keys(), freq.values()):
		if value % 2 == 0:
			even_frq.append(key)
		else:
			odd_frq.append(key)
			if value > 1:
				even_frq.append(key)
	not_poss = False
	ans = [[0 for i in range(m)] for i in range(n)]
	if len(odd_frq) != 0 and m % 2 == 0:
		not_poss = True
	if m % 2 == 1:
		if len(odd_frq) > n:
			not_poss = True
		elif n % 2 != len(odd_frq) % 2:
			not_poss = True
	if not not_poss:
		for k in range(n):
			j = m - 1
			i = 0
			while i < j:
				value = even_frq.pop()
				ans[k][i] = value
				ans[k][j] = value
				freq[value] -= 2
				if freq[value] > 1:
					even_frq.append(value)
				j -= 1
				i += 1
		if m % 2 == 1:
			even_frq += odd_frq
			for i in range(n):
				value = even_frq.pop()
				freq[value] -= 1
				if freq[value] != 0:
					even_frq.append(value)
				ans[i][m // 2] = value
	if not_poss:
		print(-1)
	else:
		for i in range(n):
			for j in range(m):
				print(ans[i][j], end=' ')
			print()


def main():
	T = int(input())
	for _ in range(T):
		(N, M) = map(int, input().split())
		A = []
		for _ in range(N):
			A.append(list(map(int, input().split())))
		masterMap = {}
		(evenMap, oddMap) = ({}, {})
		for i in range(N):
			for j in range(M):
				if A[i][j] in masterMap:
					masterMap[A[i][j]] += 1
				else:
					masterMap[A[i][j]] = 1
		for key in masterMap:
			if masterMap[key] % 2 != 0:
				oddMap[key] = masterMap[key]
			else:
				evenMap[key] = masterMap[key]
		ansMatrix = [[0 for i in range(M)] for j in range(N)]
		flag = True
		cols = M // 2 + (M % 2 != 0)
		for i in range(N):
			for j in range(cols):
				if j != M - j - 1:
					if evenMap == {}:
						for key in oddMap:
							if oddMap[key] > 1:
								ansMatrix[i][j] = key
								ansMatrix[i][M - j - 1] = key
								oddMap[key] -= 2
								break
					else:
						for key in evenMap:
							ansMatrix[i][j] = key
							ansMatrix[i][M - j - 1] = key
							evenMap[key] -= 2
							if evenMap[key] == 0:
								del evenMap[key]
							break
				elif oddMap == {}:
					for key in evenMap:
						ansMatrix[i][j] = key
						evenMap[key] -= 1
						oddMap[key] = evenMap[key]
						del evenMap[key]
						break
				else:
					for key in oddMap:
						ansMatrix[i][j] = key
						oddMap[key] -= 1
						if oddMap[key] == 0:
							del oddMap[key]
						elif oddMap[key] % 2 == 0:
							evenMap[key] = oddMap[key]
							del oddMap[key]
						break
		if oddMap == {} and evenMap == {}:
			for i in range(N):
				for j in range(M):
					print(ansMatrix[i][j], end=' ')
				print()
		else:
			print(-1)
main()


t = int(input())
for _ in range(t):
	(row, col) = map(int, input().split())
	dp = dict()
	matrix = [[0] * col for _ in range(row)]
	for i in range(row):
		temp = list(map(int, input().split()))
		for j in range(col):
			dp[temp[j]] = dp.get(temp[j], 0) + 1
	ones = []
	pairs = []
	for (key, val) in dp.items():
		left = val - val % 2
		if val % 2:
			ones.append(key)
		pairs.extend([key] * left)
	reqdLen = 2 * (col // 2) * row
	while len(pairs) > reqdLen:
		ones.append(pairs.pop())
	if len(ones) == row * (col % 2):
		for curRow in range(row):
			(l, r) = (0, col - 1)
			onePos = 0
			while l < r:
				matrix[curRow][l] = pairs.pop()
				matrix[curRow][r] = pairs.pop()
				l += 1
				r -= 1
			if l == r:
				matrix[curRow][l] = ones.pop()
		for r in range(row):
			for c in range(col):
				print(matrix[r][c], end=' ')
			print()
	else:
		print(-1)


def solve():
	(n, m) = [eval(x) for x in input().split()]
	matrix = []
	series = []
	for i in range(n):
		a = [eval(x) for x in input().split()]
		matrix.append(a)
		series = series + a
	even = []
	odd = []
	setSeries = set(series)
	for i in setSeries:
		if series.count(i) % 2 == 0:
			even.append(i)
		elif series.count(i) > 2 and series.count(i) % 2 != 0:
			odd.append(i)
			even.append(i)
		else:
			odd.append(i)
	if m % 2 != 0:
		if len(odd) > n:
			return [[-1]]
	elif len(odd) != 0:
		return [[-1]]
	if m % 2 == 0:
		p = 0
		for i in range(n):
			for j in range(m // 2):
				matrix[i][j] = series[p]
				matrix[i][m - j - 1] = series[p]
				k = series[p]
				del series[p]
				del series[series.index(k)]
	else:
		p = 0
		for i in range(n):
			for j in range(m // 2):
				while series[p] not in even or series.count(series[p]) < 2:
					p = p + 1
				matrix[i][j] = series[p]
				matrix[i][m - j - 1] = series[p]
				k = series[p]
				del series[p]
				del series[series.index(k)]
		j = 0
		for i in series:
			matrix[j][m // 2] = i
			j = j + 1
	return matrix
for z in range(int(input())):
	a = solve()
	n = len(a)
	m = len(a[0])
	for i in range(n):
		print(*a[i])


import collections
t = int(input())
for _ in range(t):
	(row, col) = map(int, input().rstrip().split())
	arr = []
	hashMap = collections.defaultdict(int)
	for _ in range(row):
		a = input().rstrip().split()
		for num in a:
			hashMap[num] += 1
		arr.append(a)
	cntOfOdd = 0
	arrOfOdds = []
	for num in hashMap:
		if hashMap[num] % 2 != 0:
			cntOfOdd += 1
			arrOfOdds.append(num)
			hashMap[num] -= 1
	if cntOfOdd > 0 and col % 2 == 0 or (col % 2 != 0 and cntOfOdd > row):
		print('-1')
	else:
		for rowPos in range(row):
			for colPos in range(col // 2):
				if colPos != col - colPos - 1:
					temp = ''
					for num in hashMap:
						if hashMap[num] != 0:
							temp = num
							break
					num = temp
					arr[rowPos][colPos] = num
					arr[rowPos][col - colPos - 1] = num
					hashMap[num] -= 2
		for num in hashMap:
			if hashMap[num] != 0:
				for i in range(hashMap[num]):
					arrOfOdds.append(num)
		if col % 2 != 0:
			for rowPos in range(0, row):
				arr[rowPos][col // 2] = arrOfOdds[rowPos]
		for posRow in range(row):
			print(' '.join(arr[posRow]))


from sys import stdin

def input():
	return stdin.readline()
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = {}
	for i in range(n):
		arr = list(map(int, input().split()))
		for j in arr:
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
	od = 0
	odarr = []
	ele = []
	for i in d:
		if d[i] % 2 != 0:
			od += 1
			odarr.append(i)
		ele.append(i)
	if m % 2 == 0 and od != 0 or (m % 2 == 1 and od > n):
		print(-1)
		continue
	arr = [[0] * m for i in range(n)]
	f = 0
	for i in range(n):
		for j in range(m // 2):
			c = ele[f]
			while d[c] <= 1:
				f = f + 1
				c = ele[f]
			arr[i][j] = c
			arr[i][m - j - 1] = c
			d[c] -= 2
			if d[c] <= 1:
				f = f + 1
	if m % 2 == 1:
		for i in range(n):
			for j in d:
				if d[j] > 0:
					arr[i][m // 2] = j
					d[j] -= 1
					break
	for i in range(n):
		for j in range(m):
			print(arr[i][j], end=' ')
		print()


try:
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		l = []
		for __ in range(n):
			row = list(map(int, input().split()))
			l.append(row)
		if n == 1 and m == 1:
			print(*row)
			continue
		listy = [i for j in l for i in j]
		length = len(listy)
		listy.sort()
		first = listy[0]
		dic = {}
		for i in range(1, length):
			if i == 1:
				dic[first] = 1
			if first == listy[i]:
				dic[first] += 1
			else:
				dic[listy[i]] = 1
			first = listy[i]
		flag = 0
		justy = [v for (k, v) in dic.items() if v % 2]
		if m % 2:
			if len(justy) <= n:
				flag = 1
		elif len(justy) == 0:
			flag = 1
		if flag:
			if m % 2:
				just_one = {k: 1 for (k, v) in dic.items() if v % 2}
				dic = {k: v - 1 if v % 2 else v for (k, v) in dic.items()}
				for j in range(n):
					new_list = []
					for z in range(m // 2):
						for (k, v) in dic.items():
							if v >= 2:
								new_list.append(k)
								dic[k] -= 2
								break
					new_list.extend(new_list[::-1])
					dic = {k: v for (k, v) in dic.items() if v != 0}
					if just_one:
						k = just_one.popitem()
						new_list.insert(m // 2, k[0])
					else:
						for (k, v) in dic.items():
							if v >= 2:
								new_list.insert(m // 2, k)
								just_one[k] = 1
								dic[k] -= 2
								break
					print(*new_list)
			else:
				for yo in range(n):
					new_list = []
					for z in range(m // 2):
						for (k, v) in dic.items():
							if v >= 2:
								new_list.append(k)
								dic[k] -= 2
								break
					new_list.extend(new_list[::-1])
					print(*new_list)
		else:
			print(-1)
except:
	pass


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = {}
	for i in range(n):
		arr = list(map(int, input().split()))
		for j in arr:
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
	od = 0
	odarr = []
	ele = []
	for i in d:
		if d[i] % 2 != 0:
			od += 1
			odarr.append(i)
		ele.append(i)
	if m % 2 == 0 and od != 0 or (m % 2 == 1 and od > n):
		print(-1)
		continue
	arr = [[0] * m for i in range(n)]
	f = 0
	for i in range(n):
		for j in range(m // 2):
			c = ele[f]
			while d[c] <= 1:
				f = f + 1
				c = ele[f]
			arr[i][j] = c
			arr[i][m - j - 1] = c
			d[c] -= 2
			if d[c] <= 1:
				f = f + 1
	if m % 2 == 1:
		for i in range(n):
			for j in d:
				if d[j] > 0:
					arr[i][m // 2] = j
					d[j] -= 1
					break
	for i in range(n):
		for j in range(m):
			print(arr[i][j], end=' ')
		print()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[]] * n
	d = dict()
	for i in range(n):
		a[i] = list(map(int, input().split()))
	for i in range(n):
		for j in range(m):
			d[a[i][j]] = 0
	for i in range(n):
		for j in range(m):
			d[a[i][j]] += 1
	if m % 2 == 0:
		x = 0
	else:
		x = n
	count = 0
	l = []
	q = []
	for i in d:
		if d[i] % 2 == 1:
			count += 1
			l.extend([i for j in range(d[i])])
			y = l.pop()
			q.append(y)
		else:
			l.extend([i for j in range(d[i])])
	if count > x:
		print('-1')
	else:
		if m % 2 == 0:
			k = 0
			for i in range(n):
				for j in range(m // 2):
					a[i][j] = l[k]
					a[i][m - j - 1] = l[k + 1]
					k += 2
		else:
			k = 0
			h = 0
			for i in range(n):
				for j in range(m // 2):
					a[i][j] = l[k]
					a[i][m - j - 1] = l[k + 1]
					k += 2
				if h == len(q):
					a[i][m // 2] = l[-1]
					l.pop()
				else:
					a[i][m // 2] = q[h]
					h += 1
		for i in range(n):
			for j in range(m):
				print(a[i][j], end=' ')
			print()


def CountFrequency(my_list):
	freq = {}
	for items in my_list:
		freq[items] = my_list.count(items)
	return freq
t = int(input())
for _ in range(t):
	nm = [int(x) for x in input().split()]
	n = nm[0]
	m = nm[1]
	el = []
	for r in range(n):
		row = [int(y) for y in input().split()]
		for c in range(m):
			el.append(row[c])
	freq = CountFrequency(el)
	flag = 0
	if m % 2 == 0:
		for f in freq.values():
			if f % 2 != 0:
				flag = 1
				print('-1')
				break
	else:
		odd = 0
		for f in freq.values():
			if f % 2 != 0:
				odd = odd + 1
		if odd > n:
			flag = 1
			print('-1')
	if flag == 0:
		even = []
		odd = []
		for (key, value) in freq.items():
			if value % 2 == 0:
				for e in range(value):
					even.append(key)
			else:
				for e in range(value - 1):
					even.append(key)
				odd.append(key)
		pointe = 0
		pointo = 0
		final_matrix = [[0 for i in range(m)] for j in range(n)]
		for i in range(n):
			for j in range(m // 2):
				final_matrix[i][j] = even[pointe]
				final_matrix[i][m - j - 1] = even[pointe]
				pointe = pointe + 2
		for i in range(n):
			if final_matrix[i][m // 2] == 0:
				if pointe < len(even):
					final_matrix[i][m // 2] = even[pointe]
					pointe = pointe + 1
				elif pointo < len(odd):
					final_matrix[i][m // 2] = odd[pointo]
					pointo = pointo + 1
		for i in range(n):
			print(*final_matrix[i])


from collections import Counter
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	l = []
	for i in range(n):
		x = list(map(int, input().split()))
		arr.append(x)
		l.extend(x)
	c = Counter(l)
	countodd = 0
	for i in c.values():
		if i % 2 == 1:
			countodd += 1
	if m % 2 == 0 and countodd != 0 or (m % 2 != 0 and countodd > n):
		print(-1)
		continue
	d = {}
	d = c
	odds = []
	for (i, j) in zip(d.keys(), d.values()):
		if j % 2 == 1:
			d[i] -= 1
			odds.append(i)
	dkey = []
	dval = []
	for i in d.items():
		dkey.append(i[0])
		dval.append(i[1])
	x = 0
	for i in range(n):
		for j in range(m // 2):
			if j != m - j - 1:
				while dval[x] == 0:
					x += 1
				arr[i][j] = dkey[x]
				arr[i][m - j - 1] = dkey[x]
				dval[x] -= 2
	for i in range(len(dval)):
		if dval[i] != 0:
			for j in range(dval[i]):
				odds.append(dkey[i])
	if m % 2 == 1:
		for i in range(len(odds)):
			arr[i][m // 2] = odds[i]
	for i in range(n):
		for j in range(m):
			print(arr[i][j], end=' ')
		print()


def solve(grid):
	(nr, nc) = (len(grid), len(grid[0]))
	counts = {}
	for row in grid:
		for v in row:
			if v not in counts:
				counts[v] = 0
			counts[v] += 1
	(odd, even) = ([], [])
	for (k, v) in counts.items():
		if v & 1:
			odd.append(k)
		else:
			even.append(k)
	if len(odd) > nr:
		return [[-1]]
	if nc % 2 == 0 and odd:
		return [[-1]]
	if nc % 2 == 1 and (nr - len(odd)) % 2 == 1:
		return [[-1]]
	if nc % 2 == 1:
		r = 0
		while r < nr:
			if odd:
				v = odd.pop()
				grid[r][nc // 2] = v
				counts[v] -= 1
				if counts[v]:
					even.append(v)
				r += 1
			else:
				v = even[-1]
				grid[r][nc // 2] = grid[r + 1][nc // 2] = v
				counts[v] -= 2
				if not counts[v]:
					even.pop()
				r += 2
	for r in range(nr):
		for c in range(nc // 2):
			v = even[-1]
			grid[r][c] = grid[r][-1 - c] = v
			counts[v] -= 2
			if not counts[v]:
				even.pop()
	return grid

def main():
	from sys import stdin
	T = int(stdin.readline().strip())
	for _ in range(T):
		(N, M) = list(map(int, stdin.readline().strip().split()))
		grid = [list(map(int, stdin.readline().strip().split())) for _ in range(N)]
		rgrid = solve(grid)
		for row in rgrid:
			print(' '.join(map(str, row)))
main()


def solve(grid):
	(nr, nc) = (len(grid), len(grid[0]))
	counts = {}
	for row in grid:
		for v in row:
			if v not in counts:
				counts[v] = 0
			counts[v] += 1
	(odd, even) = ([], [])
	for (k, v) in counts.items():
		if v & 1:
			odd.append(k)
		else:
			even.append(k)
	if len(odd) > nr:
		return [[-1]]
	if not nc & 1 and odd:
		return [[-1]]
	if nc & 1 and nr - len(odd) & 1:
		return [[-1]]
	if nc & 1:
		r = 0
		while r < nr:
			if odd:
				v = odd.pop()
				grid[r][nc // 2] = v
				counts[v] -= 1
				if counts[v]:
					even.append(v)
				r += 1
			else:
				v = even[-1]
				grid[r][nc // 2] = grid[r + 1][nc // 2] = v
				counts[v] -= 2
				if not counts[v]:
					even.pop()
				r += 2
	for r in range(nr):
		for c in range(nc // 2):
			v = even[-1]
			grid[r][c] = grid[r][-1 - c] = v
			counts[v] -= 2
			if not counts[v]:
				even.pop()
	return grid

def mine():
	from random import randint

	def check(rgrid):
		return all((row == row[::-1] for row in rgrid))
	for _ in range(10):
		N = randint(1, 5)
		M = randint(1, 5)
		grid = [[randint(1, 5) for c in range(M)] for r in range(N)]
		print('\n*** check grid=', grid)
		rgrid = solve(grid)
		if rgrid[0][0] != -1 and (not check(rgrid)):
			print('FAILED')
			return
	print('passed')

def main():
	from sys import stdin
	T = int(stdin.readline().strip())
	for _ in range(T):
		(N, M) = list(map(int, stdin.readline().strip().split()))
		grid = [list(map(int, stdin.readline().strip().split())) for _ in range(N)]
		rgrid = solve(grid)
		for row in rgrid:
			print(' '.join(map(str, row)))
main()


try:
	for _ in range(int(input())):
		(r, c) = map(int, input().split())
		list1 = []
		for i in range(r):
			l = list(map(int, input().split()))
			list1.append(l)
		dict1 = {}
		for i in range(r):
			for j in range(c):
				if list1[i][j] in dict1:
					dict1[list1[i][j]] += 1
				else:
					dict1[list1[i][j]] = 1
		sodd = 0
		seven = 0
		dict2 = {}
		dict3 = {}
		for i in dict1:
			x = dict1[i]
			if x % 2 == 0:
				seven += x
				dict2[i] = x
			else:
				sodd += 1
				dict3[i] = 1
				if i not in dict2:
					dict2[i] = x - 1
				else:
					dict2[i] += x - 1
		list11 = []
		list22 = []
		for x in dict2:
			while dict2[x]:
				list11.append(x)
				dict2[x] -= 1
		for y in dict3:
			while dict3[y]:
				list22.append(y)
				dict3[y] -= 1
		if c % 2 == 0 and sodd != 0:
			print(-1)
		elif c % 2 != 0 and sodd > r:
			print(-1)
		else:
			k = 0
			lll = []
			for i in range(r):
				lr = [0] * c
				i1 = 0
				i2 = c - 1
				while i1 <= i2:
					if i1 != i2:
						x1 = list11.pop()
						x2 = list11.pop()
						lr[i1] = x1
						lr[i2] = x2
						i1 += 1
						i2 -= 1
					else:
						if list22:
							lr[i1] = list22.pop()
						else:
							lr[i1] = list11[0 + k]
							k += 1
						i1 += 1
						i2 -= 1
				lll.append(lr)
			for i in range(r):
				for j in range(c):
					print(lll[i][j], end=' ')
				print()
except:
	pass


for _ in range(int(input())):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	d = {}
	for i in range(n):
		a = list(map(int, input().split()))
		for j in a:
			try:
				d[j] += 1
			except:
				d[j] = 1
	a = [[0 for x in range(m)] for y in range(n)]
	a1 = []
	a2 = []
	b1 = []
	b2 = []
	for (key, value) in d.items():
		if value % 2 == 0:
			a1.append(key)
			b1.append(value)
		else:
			a2.append(key)
			b2.append(value)
	for i in range(len(a2)):
		if b2[i] > 1:
			a1.append(a2[i])
			b1.append(b2[i] - 1)
		b2[i] = 1
	if m % 2 == 0:
		if len(a2) > 0:
			print('-1')
		else:
			l = 0
			for i in range(n):
				x = 0
				y = m - 1
				while x < y:
					a[i][x] = a1[l]
					a[i][y] = a1[l]
					b1[l] -= 2
					x += 1
					y -= 1
					if b1[l] == 0:
						l += 1
			for i in range(n):
				for j in range(m):
					print(a[i][j], end=' ')
				print('')
	elif len(a2) > n:
		print('-1')
	else:
		z1 = len(a1)
		z2 = len(a2)
		l1 = 0
		l2 = 0
		for i in range(n):
			x = 0
			y = m - 1
			while x < y:
				a[i][x] = a1[l1]
				a[i][y] = a1[l1]
				x += 1
				y -= 1
				b1[l1] -= 2
				if b1[l1] == 0:
					l1 += 1
		ind = n
		for i in range(n):
			if l2 == z2:
				ind = i
				break
			x = m // 2
			a[i][x] = a2[l2]
			l2 += 1
		for i in range(ind, n):
			x = m // 2
			a[i][x] = a1[l1]
			b1[l1] -= 1
			if b1[l1] == 0:
				l1 += 1
		for i in range(n):
			for j in range(m):
				print(a[i][j], end=' ')
			print('')


ans = []
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = {}
	l = []
	pair = []
	single = []
	for i in range(n):
		l = list(map(int, input().split()))
		for j in range(m):
			if l[j] in d:
				if d[l[j]] == 1:
					pair.append(l[j])
					single.remove(l[j])
					d[l[j]] = 0
				else:
					d[l[j]] += 1
					single.append(l[j])
			else:
				d[l[j]] = 1
				single.append(l[j])
	flag = 0
	evuse = []
	if m % 2 == 0 and len(single) > 0:
		flag = 1
	if m % 2 == 1 and n % 2 == 1 and (len(single) < 1):
		flag = 1
	if len(single) > n:
		flag = 1
	if flag == 1:
		ans.append([-1])
	else:
		for i in range(n):
			s = [0] * m
			for i in range(m // 2):
				cha = pair.pop()
				s[i] = cha
				s[m - i - 1] = cha
			if m % 2 == 1:
				if len(single) > 0:
					s[m // 2] = single.pop()
				elif len(evuse) > 0:
					s[m // 2] = evuse.pop()
				else:
					cha = pair.pop()
					s[m // 2] = cha
					evuse.append(cha)
			ans.append(s)
for i in range(len(ans)):
	for j in range(len(ans[i])):
		print(ans[i][j], end=' ')
	print()


def print_matrix(mat):
	for row in mat:
		print(' '.join((str(x) for x in row)))
for i in range(int(input())):
	(n, m) = map(int, input().split())
	all_elems = []
	final_mat = []
	for k in range(n):
		row = list(map(int, input().split()))
		all_elems.extend(row)
	counts_dict = {}
	odd_list = []
	cont_boo = True
	for item in set(all_elems):
		cnt = all_elems.count(item)
		if m % 2 == 0:
			if cnt % 2 != 0:
				cont_boo = False
				break
		elif cnt % 2 != 0:
			odd_list.append(item)
		counts_dict[item] = cnt
	if m % 2 == 0 and cont_boo:
		for x in range(n):
			this_row = []
			for y in range(int(m / 2)):
				for (key, value) in counts_dict.items():
					if value > 0:
						this_row.append(key)
						counts_dict[key] -= 2
						break
			this_row.extend(this_row[::-1])
			final_mat.append(this_row)
		print_matrix(final_mat)
	elif len(odd_list) <= n and cont_boo and ((n - len(odd_list)) % 2 == 0):
		for x in range(n):
			this_row = []
			for y in range(int(m / 2)):
				for (key, value) in counts_dict.items():
					if value > 1:
						this_row.append(key)
						counts_dict[key] -= 2
						break
			this_row.extend(this_row[::-1])
			halfway = int((m - 1) / 2)
			if len(odd_list) > 0:
				this_row.insert(halfway, odd_list[0])
				counts_dict[odd_list[0]] -= 1
				odd_list.pop(0)
			else:
				for (key, value) in counts_dict.items():
					if value > 0 and value % 2 == 0:
						this_row.insert(halfway, key)
						counts_dict[key] -= 1
						odd_list.append(key)
						break
			final_mat.append(this_row)
		print_matrix(final_mat)
	else:
		print(-1)


try:
	t = int(input())
	while t >= 0:
		t = t - 1
		rc = list(map(int, input().split()))
		n = int(rc[0])
		m = int(rc[1])
		l = []
		unique_list = []
		for i in range(n):
			r = list(map(int, input().split()))
			for x in r:
				if x not in unique_list:
					unique_list.append(x)
				else:
					unique_list.remove(x)
					l.append(x)
					l.append(x)
		if m % 2 == 0 and len(unique_list) != 0 or (m % 2 != 0 and len(unique_list) > n):
			print('-1')
			continue
		l.sort()
		if m % 2 == 0:
			res = []
			for i in range(n):
				row = []
				k = 0
				for j in range(0, m, 2):
					x = l.pop()
					x = l.pop()
					row.insert(k, x)
					row.insert(k, x)
					k = k + 1
				res.append(row)
		else:
			while len(unique_list) < n:
				unique_list.append(l.pop())
			res = []
			for i in range(n):
				row = []
				k = 0
				while k <= m / 2:
					if k < int(m / 2):
						x = l.pop()
						x = l.pop()
						row.insert(k, x)
						row.insert(k, x)
						k = k + 1
					else:
						x = unique_list.pop()
						row.insert(k, x)
						break
				res.append(row)
		for row in res:
			for x in row:
				print(x, end=' ')
			print('')
except:
	pass


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	l = [[int(x) for x in input().split()] for y in range(n)]
	d = {}
	for i in l:
		for j in i:
			try:
				d[j] += 1
			except:
				d[j] = 1
	singles = []
	temp = d.copy()
	for i in temp:
		if temp[i] & 1:
			singles.append(i)
			if temp[i] == 1:
				del d[i]
			else:
				d[i] -= 1
	doubles = list(d.keys())
	if singles and (not m & 1):
		print(-1)
	elif len(singles) > n:
		print(-1)
	else:
		ans = []
		for i in range(n):
			row = []
			for j in range(m // 2):
				if d[doubles[0]] > 1:
					row.append(doubles[0])
					if d[doubles[0]] == 2:
						del d[doubles[0]]
						del doubles[0]
					else:
						d[doubles[0]] -= 2
				else:
					row.append(doubles[1])
					if d[doubles[1]] == 2:
						del d[doubles[1]]
						del doubles[1]
					else:
						d[doubles[1]] -= 2
			if m & 1:
				try:
					row.append(singles[0])
					del singles[0]
				except:
					row.append(doubles[0])
					if d[doubles[0]] == 1:
						del d[doubles[0]]
						del doubles[0]
					else:
						d[doubles[0]] -= 1
			if m > 1:
				row += row[m // 2 - 1::-1]
			ans.append(row)
		for i in ans:
			for j in i[:-1]:
				print(j, end=' ')
			print(i[-1])


from fractions import Fraction
import bisect
import os
from collections import Counter
import bisect
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce, cmp_to_key
from collections import deque
import threading
from itertools import combinations
from io import BytesIO, IOBase
from itertools import accumulate

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
for _ in range(iinput()):
	(n, m) = rinput()
	mat = []
	for i in range(n):
		mat.append(rlinput())
	d = defaultdict(int)
	pairs = []
	for i in range(n):
		for j in range(m):
			d[mat[i][j]] += 1
	need = n * (m // 2)
	for i in d:
		need -= d[i] // 2
	if need > 0:
		print(-1)
		continue
	newmat = []
	dq = deque()
	extra = []
	for i in d:
		for j in range(d[i] // 2):
			dq.append(i)
			dq.appendleft(i)
		if d[i] % 2:
			extra.append(i)
	for i in range(n):
		ans = deque()
		for j in range(m // 2):
			ans.append(dq.pop())
			ans.appendleft(dq.popleft())
		ans = list(ans)
		newmat.append(ans)
	if m % 2:
		extra += list(dq)
		remove = -1
		for i in range(n):
			newmat[i].insert(m // 2, extra[remove])
			remove -= 1
	for i in newmat:
		print(*i)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = []
	a = []
	d = {}
	for i in range(n):
		a = input().split()
		m.append(a)
		a = []
	for i in range(n):
		for j in range(k):
			if int(m[i][j]) in d:
				d[int(m[i][j])] += 1
			else:
				d[int(m[i][j])] = 1
	noofpairs = 0
	pairlist = []
	unique = []
	for i in d:
		if d[i] == 1:
			unique.append(i)
		else:
			noofpairs += d[i] // 2
			for c in range(d[i] // 2):
				pairlist.append(i)
	pairsreq = k // 2 * n
	if noofpairs < pairsreq:
		print(-1)
	else:
		b = 0
		nwmat = []
		newlist = []
		for i in range(n):
			newlist = []
			for j in range(k // 2):
				newlist.insert(0, pairlist[b])
				newlist.append(pairlist[b])
				d[pairlist[b]] -= 2
				b += 1
			nwmat.append(newlist)
		if k % 2 == 1:
			u = []
			for i in d:
				for j in range(d[i]):
					u.append(i)
			for i in range(n):
				nwmat[i].insert(k // 2, u[i])
		for i in range(n):
			print(*nwmat[i])


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().rstrip().split()))
	nums = {}
	for _ in range(n):
		s = list(map(int, input().rstrip().split()))
		for i in s:
			if nums.get(i) is None:
				nums[i] = 1
			else:
				nums[i] += 1
	odd = 0
	for i in nums:
		if nums[i] % 2 != 0:
			odd += 1
	if m % 2 == 0:
		if odd > 0:
			print(-1)
			continue
	elif odd > n:
		print(-1)
		continue
	for i in range(n):
		temp = [0 for _ in range(m)]
		if m % 2 == 0:
			mid = m // 2
		else:
			mid = m // 2 + 1
			for i in nums:
				if nums[i] % 2 != 0:
					temp[m // 2] = str(i)
					nums[i] -= 1
					break
			if temp[m // 2] == 0:
				for i in nums:
					if nums[i] > 0:
						temp[m // 2] = str(i)
						nums[i] -= 1
						break
		index = 0
		while mid < m:
			for i in nums:
				if nums[i] >= 2 and nums[i] > 0:
					temp[index] = temp[m - 1 - index] = str(i)
					nums[i] -= 2
					break
			mid += 1
			index += 1
		print(' '.join(map(str, temp)))


for t in range(int(input())):
	(N, M) = map(int, input().split())
	A = []
	flag = False
	for i in range(N):
		z = input()
		if z != z[::-1]:
			flag = True
		A.append(z.split())
	if flag == False:
		for i in A:
			print(' '.join(i))
		continue
	d = []
	single = set()
	count1 = 0
	count2 = 0
	for i in range(N):
		for j in range(M):
			if A[i][j] not in single:
				single.add(A[i][j])
			else:
				single.remove(A[i][j])
				d.append(A[i][j])
				count2 += 2
	count1 = len(single)
	single = list(single)
	if M % 2 == 0 and count1 > 0 or (M % 2 != 0 and (N - count1 < 0 or (N - count1) % 2 != 0)):
		print(-1)
	elif M % 2 == 0:
		i = 0
		for k in range(N):
			s = ''
			for j in range(M // 2):
				if s == '':
					s = d[i] + ' ' + d[i]
				else:
					s = d[i] + ' ' + s + ' ' + d[i]
				i += 1
			print(s)
	else:
		i = 0
		if N - count1 > 0:
			i += (N - count1) // 2
			single.extend(d[0:i] + d[0:i])
		if len(single) != N:
			print(-1)
			continue
		for k in range(N):
			s = single.pop()
			for j in range(M // 2):
				s = d[i] + ' ' + s + ' ' + d[i]
				i += 1
			print(s)


from collections import Counter
from itertools import chain

def rearrange(N, M, A):
	C = Counter()
	list(map(C.update, A))
	even = set((k for (k, v) in C.items() if v % 2 == 0))
	odd = set((k for (k, v) in C.items() if v % 2 == 1))
	C.subtract(odd)
	avail = C.elements()
	B = []
	try:
		for _ in range(N):
			row = [0] * M
			for k in range(M // 2):
				e1 = next(avail)
				e2 = next(avail)
				(row[k], row[M - k - 1]) = (e1, e2)
			B.append(row)
		rest = list(chain(avail, odd))
		if M % 2 != 0 and len(rest) != N:
			return None
		for (k, v) in enumerate(rest):
			B[k][M // 2] = v
	except StopIteration:
		return None
	return B
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	A = [list(map(int, input().split())) for _ in range(N)]
	B = rearrange(N, M, A)
	if not B:
		print(-1)
	else:
		for a in B:
			print(' '.join(map(str, a)))


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	quantity = []
	elements = []
	a = []
	for _ in range(n):
		line = list(map(int, input().split()))
		a.append(line)
		for e in line:
			if e in elements:
				quantity[elements.index(e)] += 1
			else:
				elements.append(e)
				quantity.append(1)
	odd = 0
	odds = []
	for i in range(len(quantity)):
		if quantity[i] % 2 != 0:
			odd += 1
			odds.append(i)
	if m == 1 or (m % 2 == 0 and odd == 0) or (m % 2 != 0 and odd <= n and ((n - odd) % 2 == 0)):
		k = 0
		if m % 2 != 0 and m != 1:
			p = int(m / 2)
			i = 0
			for eOdd in odds:
				a[i][p] = elements[eOdd]
				quantity[eOdd] -= 1
				i += 1
			while i < n:
				while k < len(elements) and quantity[k] == 0:
					k += 1
				if k < len(elements) and quantity[k] > 0:
					a[i][p] = elements[k]
					quantity[k] -= 1
					i += 1
		for i in range(n):
			for j in range(int(m / 2)):
				while k < len(elements) and quantity[k] < 2:
					k += 1
				if k < len(elements) and quantity[k] >= 2:
					a[i][j] = elements[k]
					a[i][m - j - 1] = elements[k]
					quantity[k] -= 2
		for i in range(n):
			for j in range(m - 1):
				print(a[i][j], end=' ')
			print(a[i][m - 1])
	else:
		print(-1)


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	quantity = []
	elements = []
	a = []
	for _ in range(n):
		line = list(map(int, input().split()))
		a.append(line)
		for e in line:
			if e in elements:
				quantity[elements.index(e)] += 1
			else:
				elements.append(e)
				quantity.append(1)
	odd = 0
	for q in quantity:
		if q % 2 != 0:
			odd += 1
	if m == 1 or (m % 2 == 0 and odd == 0) or (m % 2 != 0 and odd <= n and ((n - odd) % 2 == 0)):
		for i in range(n):
			for j in range(m - 1):
				print(a[i][j], end=' ')
			print(a[i][m - 1])
	else:
		print(-1)


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	quantity = []
	elements = []
	a = []
	for _ in range(n):
		line = list(map(int, input().split()))
		a.append(line)
		for e in line:
			if e in elements:
				quantity[elements.index(e)] += 1
			else:
				elements.append(e)
				quantity.append(1)
	odd = 0
	for i in range(len(quantity)):
		if quantity[i] % 2 != 0:
			odd += 1
	possible = False
	if m % 2 == 0 and odd == 0:
		possible = True
	elif m == 1:
		possible = True
	elif m % 2 != 0 and odd <= n and ((n - odd) % 2 == 0):
		possible = True
	if possible == False:
		print(-1)
	else:
		for i in range(n):
			for j in range(m - 1):
				print(a[i][j], end=' ')
			print(a[i][m - 1])


t = int(input())

def putelement(b, row, col, num, n, m):
	b[row][col] = num
	b[row][m - col - 1] = num
	col += 1
	if not col < m // 2:
		row += 1
		col = 0
	return [row, col]
for _ in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	odd = []
	ans = 0
	b = []
	row = 0
	col = 0
	for i in range(n):
		b.append([0] * m)
	for i in range(n):
		for j in range(m):
			if l[i][j] not in odd:
				odd.append(l[i][j])
			elif row < n and col < m // 2:
				odd.remove(l[i][j])
				v = putelement(b, row, col, l[i][j], n, m)
				row = v[0]
				col = v[1]
			else:
				odd.append(l[i][j])
	if m % 2 == 0:
		if len(odd) > 0:
			print(-1)
			ans = 1
	elif len(odd) > n:
		print(-1)
		ans = 1
	if ans == 0:
		if m % 2 != 0:
			for i in range(n):
				b[i][m // 2] = odd.pop(-1)
		for i in b:
			print(*i)


from collections import Counter
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	ls = []
	c = Counter()
	for i in range(N):
		k = list(map(int, input().strip().split()))
		ls.append(k)
		c.update(k)
	e = 0
	odd = []
	for i in c.keys():
		e += c[i] // 2
	x = M // 2 * N
	if e < x:
		print(-1)
	else:
		for i in range(N):
			s = [0] * M
			l = 0
			flag = 0
			for i in c.keys():
				while c[i] > 1:
					if l == M // 2:
						flag = 1
						break
					c[i] -= 2
					s[l] = i
					s[M - l - 1] = i
					l += 1
				if flag == 1:
					break
			if M % 2 == 1:
				j = 0
				for i in c.keys():
					if c[i] % 2 == 1:
						j = 1
						s[M // 2] = i
						c[i] -= 1
						break
				if j == 0:
					for i in c.keys():
						if c[i] >= 1:
							s[M // 2] = i
							c[i] -= 1
							break
			print(' '.join(map(str, s)))


T = int(input())
F = []
for i in range(T):
	a = input()
	L = []
	(N, M) = tuple(map(int, a.split()))
	for j in range(N):
		b = input()
		L += list(map(int, b.split()))
	L.sort()
	S = set(L)
	D = {}
	(A, B) = ([], [])
	(P, Q) = ([], [])
	for j in S:
		D[j] = L.count(j)
		if D[j] % 2 == 0:
			A += [j]
		else:
			B += [j]
	if M % 2 == 0 and len(B) != 0 or (M % 2 == 1 and (N < len(B) or (N - len(B)) % 2 == 1)):
		F += [-1]
		continue
	for j in A:
		P += [j] * D[j]
	for j in B:
		Q += [j]
		P += [j] * (D[j] - 1)
	if M % 2 == 1:
		while len(Q) != N:
			Q += P[:2]
			P = P[2:]
	if M % 2 == 0:
		for j in range(N):
			X = []
			x = ''
			for k in range(M // 2):
				X += [P[0]]
				P = P[2:]
			X += X[::-1]
			for t in X:
				x += str(t) + ' '
			F += [x[:-1]]
	else:
		for j in range(N):
			X = []
			x = ''
			for k in range(M // 2):
				X += [P[0]]
				P = P[2:]
			X += [Q[j]] + X[::-1]
			for t in X:
				x += str(t) + ' '
			F += [x[:-1]]
for i in F:
	print(i)


t = int(input())
while t != 0:
	t -= 1
	(n, m) = map(int, input().split(' '))
	a = []
	for i in range(n):
		x = list(map(int, input().split(' ')))
		a.append(x)
	dp = {}
	for i in range(n):
		for j in range(m):
			if a[i][j] in dp:
				dp[a[i][j]] += 1
			else:
				dp[a[i][j]] = 1
	if m % 2 == 0:
		p = 0
		for i in dp.values():
			if i % 2 == 1:
				p = 1
				break
		if p == 1:
			print('-1')
		else:
			x = []
			b = [0] * m
			(s, e) = (0, m - 1)
			for (k, v) in dp.items():
				j = 0
				while j != v:
					if j % 2 == 0:
						b[s] = k
						s += 1
					else:
						b[e] = k
						e -= 1
					j += 1
					if s > e:
						x.append(b)
						b = [0] * m
						s = 0
						e = m - 1
			for i in range(n):
				for j in range(m):
					print(x[i][j], end=' ')
				print()
	else:
		p = 0
		c = 0
		for i in dp.values():
			if i % 2 == 1:
				c += 1
		if c > n:
			print('-1')
		elif m == 1:
			for i in range(n):
				for j in range(m):
					print(a[i][j], end=' ')
				print()
		else:
			x = []
			b = [0] * m
			(s, e) = (0, m - 1)
			o = []
			u = 0
			for (k, v) in dp.items():
				j = 0
				r = v
				if u == 1:
					while j != v:
						o.append(k)
						j += 1
				if v % 2 == 1 and u == 0:
					r = v - 1
					o.append(k)
				while j != r and len(x) < n and (u == 0):
					if j % 2 == 0:
						b[s] = k
						s += 1
					else:
						b[e] = k
						e -= 1
					j += 1
					if s >= e:
						x.append(b)
						b = [0] * m
						s = 0
						e = m - 1
						if len(x) == n:
							u = 1
							while j != r:
								o.append(k)
								j += 1
			z = m // 2
			for i in range(n):
				x[i][z] = o[i]
			h = 0
			for i in range(n):
				for j in range(m // 2):
					if x[i][j] != x[i][m - 1 - j]:
						h = 1
						break
			if h == 0:
				for i in range(n):
					for j in range(m):
						print(x[i][j], end=' ')
					print()
			else:
				print('-1')


t = int(input())
for _ in range(t):
	dp = {}
	(row, col) = (int(var) for var in input().split(' '))
	for _ in range(row):
		for element in [int(var) for var in input().split(' ')]:
			dp[element] = dp.get(element, 0) + 1
	ones = []
	pairs = []
	finalAns = [[None for _ in range(col)] for _ in range(row)]
	for (element, values) in dp.items():
		left = values - values % 2
		if values % 2 != 0:
			ones.append(element)
		if left != 0:
			for _ in range(left):
				pairs.append(element)
	reqdLen = 2 * (col // 2) * row
	while len(pairs) > reqdLen:
		ones.append(pairs.pop())
	if len(ones) == row * (col % 2):
		pos = 0
		onePos = 0
		for currRow in range(row):
			(l, r) = (0, col - 1)
			while l < r:
				(finalAns[currRow][l], finalAns[currRow][r]) = (pairs[pos], pairs[pos + 1])
				pos += 2
				l += 1
				r -= 1
			if l == r:
				finalAns[currRow][l] = ones[onePos]
				onePos += 1
		for tempRow in finalAns:
			for val in tempRow:
				print(val, end=' ')
			print()
	else:
		print(-1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mat = []
	d = {}
	count = 0
	for i in range(n):
		arr = list(map(int, input().split()))
		for j in arr:
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
			if d[j] % 2 == 0:
				count -= 1
			else:
				count += 1
	new_mat = [[0] * m for i in range(n)]
	k = list(d.keys())
	if m % 2 == 0:
		if count == 0:
			for i in range(n):
				for j in range(m // 2):
					v = k[0]
					new_mat[i][j] = v
					new_mat[i][-j - 1] = v
					d[v] -= 2
					if d[v] == 0:
						k.pop(0)
			for i in new_mat:
				print(*i)
		else:
			print(-1)
	elif count <= n:
		x = 0
		for i in range(n):
			for j in range(m // 2):
				v = k[x]
				while d[v] == 1:
					x += 1
					v = k[x]
				new_mat[i][j] = v
				new_mat[i][-j - 1] = v
				d[v] -= 2
				if d[v] == 0:
					k.pop(x)
		new_k = list(d.keys())
		for i in range(n):
			v = new_k[0]
			while d[v] == 0:
				new_k.pop(0)
				v = new_k[0]
			if d[v] > 0:
				new_mat[i][m // 2] = v
				d[v] -= 1
			if d[v] == 0:
				new_k.pop(0)
		for i in new_mat:
			print(*i)
	else:
		print(-1)


from sys import stdin

def check_condition(matrix, n, m):
	chef = []
	chefina = []
	for j in range(n):
		if j % 2 == 0:
			chef.append(matrix[j])
			chefina.append(matrix[j][::-1])
		else:
			chef.append(matrix[j][::-1])
			chefina.append(matrix[j])
	if chef == chefina:
		return 1
	else:
		return 0
tc = int(stdin.readline())
for i in range(tc):
	(n, m) = map(int, stdin.readline().split())
	matrix = []
	for j in range(n):
		matrix.append(list(map(int, stdin.readline().split())))
	num_required = n * (m // 2)
	if num_required == 0:
		for each1 in matrix:
			for each in each1:
				print(each, end=' ')
			print()
	else:
		flag = check_condition(matrix, n, m)
		if flag == 1:
			for each1 in matrix:
				for each in each1:
					print(each, end=' ')
				print()
		else:
			dict1 = {}
			list1 = []
			list2 = []
			for each1 in matrix:
				for each in each1:
					if each in dict1.keys():
						dict1[each] += 1
					else:
						dict1[each] = 1
			for (key, value) in dict1.items():
				list1.extend([key] * (value // 2))
				if value % 2 == 1:
					list2.append(key)
			if len(list1) < num_required:
				print(-1)
			else:
				list1.sort()
				list2.extend(list1[num_required:] * 2)
				list2.sort()
				list1 = list1[:num_required]
				answer = []
				y = m // 2
				for x in range(n):
					temp = []
					temp.extend(list1[:y])
					if m % 2 == 1:
						temp.append(list2.pop(0))
					temp.extend(list1[:y][::-1])
					answer.append(temp)
					list1 = list1[y:]
				for each in answer:
					for each1 in each:
						print(each1, end=' ')
					print()


for _ in range(int(input())):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	arr = []
	flag = 0
	for i in range(n):
		a = list(map(int, input().split()))
		arr.extend(a)
	freq = {}
	for items in arr:
		freq[items] = arr.count(items)
	if m % 2 == 0:
		for (key, value) in freq.items():
			if value % 2 != 0:
				print(-1)
				flag = 1
				break
		if flag == 0:
			for i in range(n):
				a = [0] * m
				for i in range(m // 2):
					x = arr[0]
					a[i] = x
					a[-i - 1] = x
					arr.remove(x)
					arr.remove(x)
				print(*a)
	else:
		count = 0
		arr_odd = []
		for (key, value) in freq.items():
			if value % 2 != 0:
				arr_odd.append(key)
				arr.remove(key)
				count += 1
		if count > n:
			print(-1)
		else:
			while count < n:
				y = arr[0]
				arr_odd.append(y)
				arr_odd.append(y)
				arr.remove(y)
				arr.remove(y)
				count += 2
			for i in range(n):
				a = [0] * m
				a[(m - 1) // 2] = arr_odd[0]
				arr_odd.remove(arr_odd[0])
				for i in range(m // 2):
					x = arr[0]
					a[i] = x
					a[-i - 1] = x
					arr.remove(x)
					arr.remove(x)
				print(*a)


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	fre = {}
	l = []
	for i in range(n):
		temp = list(map(int, input().split()))
		l.append(temp)
	for i in range(n):
		for j in range(m):
			if l[i][j] in fre:
				fre[l[i][j]] += 1
			else:
				fre[l[i][j]] = 1
	odd = 0
	even = 0
	oddelement = {}
	evenelement = {}
	evenlist = []
	oddlist = []
	for p in fre:
		if fre[p] % 2 == 0:
			even += 1
			evenelement[p] = fre[p]
			for i in range(fre[p] // 2):
				evenlist.append(p)
		else:
			odd += 1
			oddelement[p] = 1
			oddlist.append(p)
			if fre[p] > 1:
				evenelement[p] = fre[p] - 1
				for i in range((fre[p] - 1) // 2):
					evenlist.append(p)
	oddindex = 0
	evenindex = 0
	if len(oddlist) > n:
		print('-1')
		continue
	if m % 2 == 0 and odd != 0 or (m % 2 == 1 and (n % 2 == 0 and odd % 2 != 0 or (n % 2 == 1 and odd % 2 != 1))):
		print('-1')
		continue
	elif m % 2 == 0:
		for _ in range(n):
			temp = []
			for i in range(m // 2):
				print(evenlist[evenindex], end=' ')
				temp.append(evenlist[evenindex])
				evenindex += 1
			for q in range(m // 2 - 1, -1, -1):
				print(temp[q], end=' ')
			print('')
	else:
		if len(oddlist) < n:
			popo = n - len(oddlist)
			for i in range(popo // 2):
				oddlist.append(evenlist[i])
				oddlist.append(evenlist[i])
			evenlist = evenlist[popo // 2:]
		for _ in range(n):
			temp = []
			for i in range(m // 2):
				print(evenlist[evenindex], end=' ')
				temp.append(evenlist[evenindex])
				evenindex += 1
			print(oddlist[oddindex], end=' ')
			oddindex += 1
			for q in range(m // 2 - 1, -1, -1):
				print(temp[q], end=' ')
			print('')


def display(arr):
	for i in arr:
		final = ''
		for j in i:
			final += str(j) + ' '
		print(final)

def solve():
	(n, m) = map(int, input().split())
	d = {}
	x = []
	y = []
	for i in range(0, n):
		k = list(map(int, input().split()))
		x.append(k)
		y.append([0] * m)
		for i in k:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	i1 = 0
	j1 = 0
	f = 0
	num_odd = 0
	for i in d:
		if d[i] % 2 == 1:
			num_odd += 1
	if m % 2 == 0:
		if num_odd > 0:
			print(-1)
			return
		else:
			for i in d:
				for j in range(0, int(d[i] / 2)):
					y[i1][j1] = i
					y[i1][m - j1 - 1] = i
					if j1 == int(m / 2) - 1:
						j1 = 0
						i1 += 1
					else:
						j1 += 1
	else:
		if num_odd > n:
			print(-1)
			return
		for i in d:
			if d[i] % 2 == 0:
				for j in range(0, int(d[i] / 2)):
					if i1 < n and j1 < int(m / 2):
						y[i1][j1] = i
						y[i1][m - j1 - 1] = i
						if j1 == int(m / 2) - 1:
							j1 = 0
							i1 += 1
						else:
							j1 += 1
					else:
						y[f][int(m / 2)] = i
						y[f + 1][int(m / 2)] = i
						f += 2
		for i in d:
			if d[i] % 2 == 1:
				y[f][int(m / 2)] = i
				f += 1
				d[i] -= 1
				for j in range(0, int(d[i] / 2)):
					if i1 < n and j1 < int(m / 2):
						y[i1][j1] = i
						y[i1][m - j1 - 1] = i
						if j1 == int(m / 2) - 1:
							j1 = 0
							i1 += 1
						else:
							j1 += 1
					else:
						y[f][int(m / 2)] = i
						y[f + 1][int(m / 2)] = i
						f += 2
	display(y)
t = int(input())
for tt in range(0, t):
	solve()


import math

def reshape(the_list, r, c):
	if r * c != len(the_list):
		raise ValueError('Invalid new shape')
	return [the_list[tr * c:(tr + 1) * c] for tr in range(0, r)]
t = int(input())
for test_case in range(0, t):
	(r, c) = [int(x) for x in input().split(' ')]
	mat = []
	mat_map = {}
	possible = True
	for i in range(0, r):
		row = [int(x) for x in input().split(' ')]
		mat.append(row)
		for val in row:
			if val in mat_map:
				mat_map[val] += 1
			else:
				mat_map[val] = 1
	evens = 0
	odds = 0
	for value in mat_map.values():
		if value % 2 == 0:
			evens += 1
		else:
			odds += 1
	if c % 2 == 0:
		if odds > 0:
			possible = False
	elif odds > r:
		possible = False
	elif odds < r:
		if (r - odds) % 2 != 0:
			possible = False
	if possible:
		r_max = r
		c_max = math.floor(c / 2)
		full = False
		max_count = r_max * c_max
		singles = []
		new_arr = []
		for (key, value) in mat_map.items():
			remaining = max_count - len(new_arr)
			if value % 2 != 0:
				singles.append(key)
				value -= 1
			if remaining == 0:
				singles += [key] * value
			elif int(value / 2) <= remaining:
				new_arr += [key] * int(value / 2)
			else:
				new_arr += [key] * remaining
				singles += [key] * (value - 2 * remaining)
		new_arr_2 = reshape(new_arr, r_max, c_max)
		if len(singles) == 0:
			for row_pos in range(0, r_max):
				temp_arr = new_arr_2[row_pos] + new_arr_2[row_pos][::-1]
				print(' '.join([str(x) for x in temp_arr]))
		else:
			for row_pos in range(0, r_max):
				temp_arr = new_arr_2[row_pos] + [singles[row_pos]] + new_arr_2[row_pos][::-1]
				print(' '.join([str(x) for x in temp_arr]))
	else:
		print('-1')


from collections import Counter

def genPal(d, s):
	a = [None] * s
	i = 0
	m = s // 2
	while i < m:
		for (x, y) in d.items():
			if y >= 2:
				(a[i], a[-i - 1]) = (x, x)
				d[x] -= 2
				break
		else:
			return (d, [-10000000.0])
		i += 1
	if s % 2 == 1:
		for (x, y) in d.items():
			if y == 1:
				a[m] = x
				d[x] -= 1
				return (d, a)
		for (x, y) in d.items():
			if y % 2 == 1:
				a[m] = x
				d[x] -= 1
				return (d, a)
		for (x, y) in d.items():
			if y > 1:
				a[m] = x
				d[x] -= 1
				return (d, a)
		return (d, [-10000000.0])
	else:
		return (d, a)
for _t in range(int(input())):
	(n, m) = list(map(int, input().split()))
	mat = []
	for i in range(n):
		mat.extend(list(map(int, input().split())))
	d = Counter(mat)
	ans = []
	for i in range(n):
		(d, v) = genPal(d, m)
		if -10000000.0 in v:
			print(-1)
			break
		else:
			ans.append(v)
	else:
		for i in ans:
			print(*i)


from collections import deque
T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	D = dict()
	A = []
	for i in range(n):
		A.append(list(map(int, input().split())))
		for j in range(m):
			if A[i][j] in D:
				D[A[i][j]] += 1
			else:
				D[A[i][j]] = 1
	noo = 0
	for x in D:
		if D[x] % 2 != 0:
			noo += 1
	if m % 2 == 0:
		if noo:
			print(-1)
			continue
	elif noo > n:
		print(-1)
		continue
	odds = deque([])
	evens = deque([])
	for x in D:
		if D[x] % 2 == 0:
			evens.append(x)
		else:
			odds.append(x)
	answer = []
	for i in range(n):
		s = deque([])
		if m % 2 == 1:
			if odds:
				s.append(odds[0])
				D[odds[0]] -= 1
				el = odds.popleft()
				if D[el] > 0:
					evens.append(el)
			else:
				s.append(evens[0])
				D[evens[0]] -= 1
				el = evens.popleft()
				odds.append(el)
		for j in range(m // 2):
			if evens:
				el = evens[0]
				s.appendleft(el)
				s.append(el)
				D[el] -= 2
				if D[el] == 0:
					evens.popleft()
			else:
				el = odds[0]
				s.appendleft(el)
				s.append(el)
				D[el] -= 2
		for x in s:
			print(x, end=' ')
		print()


from collections import Counter

def print_row(row, mid=None):
	left = [e for (i, e) in enumerate(row) if i % 2 == 0]
	right = [e for (i, e) in enumerate(row) if i % 2 == 1]
	if mid:
		final_row = left + [mid] + right
	else:
		final_row = left + right
	print(' '.join(map(str, final_row)))
T = int(input())
NOT_POSSIBLE = -1
for test_case in range(1, T + 1):
	(N, M) = map(int, input().split())
	all_elements = []
	for row in range(N):
		all_elements.extend(list(map(int, input().split())))
	all_counts = dict(Counter(all_elements).most_common())
	odd_count_elements = []
	for (elem, count) in all_counts.items():
		if count % 2 == 1:
			odd_count_elements.append(elem)
			all_counts[elem] -= 1
	if M % 2 == 0:
		if odd_count_elements:
			print(NOT_POSSIBLE)
		else:
			all_elements.sort()
			for row in range(N):
				print_row(all_elements[row * M:(row + 1) * M])
	else:
		ocel = len(odd_count_elements)
		if ocel > N or (N - ocel) % 2 != 0:
			print(NOT_POSSIBLE)
		else:
			all_elements.sort()
			for oce in odd_count_elements:
				all_elements.remove(oce)
			if ocel < N:
				for i in range(N - ocel):
					odd_count_elements.append(all_elements.pop())
			for row in range(N):
				print_row(all_elements[row * (M - 1):(row + 1) * (M - 1)], mid=odd_count_elements.pop())


from collections import Counter
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	matrix = []
	for i in range(n):
		matrix.append(list(map(int, input().split())))
	count = Counter()
	for i in range(n):
		for j in range(m):
			count[matrix[i][j]] += 1
	odd_possible = 0
	if m % 2 == 1:
		odd_possible = n
	freq = list(count.values())
	odd_values = 0
	for i in freq:
		if i % 2 == 1:
			odd_values += 1
	if odd_values > odd_possible:
		print(-1)
	else:
		odd_list = []
		even_list = []
		for i in count:
			if count[i] % 2 == 1:
				odd_list.append(i)
				even_list += [i] * ((count[i] - 1) // 2)
			else:
				even_list += [i] * (count[i] // 2)
		answer = []
		if odd_possible == 0:
			i = 0
			step = m // 2
			for j in range(n):
				half = even_list[i:i + step]
				o_half = half[::-1]
				answer.append(half + o_half)
				i += step
		else:
			i = 0
			step = m // 2
			for j in range(n):
				half = even_list[i:i + step]
				o_half = half[::-1]
				if odd_list == []:
					odd_list += [even_list[i + step]] * 2
					i += 1
				middle = odd_list.pop()
				answer.append(half + [middle] + o_half)
				i += step
		for i in answer:
			print(*i)