Consider a grid A with dimensions N \times M, such that all elements of the grid are distinct.

A remote controlled car is present at cell (1,1). Chef and Chefina will alternatively move the car with Chef starting first.

If it is Chef's turn, he will move the car to either right or down by 1 cell. He moves the car to the cell having larger element.
If it is Chefina's turn, she will move the car to either right or down by 1 cell. She moves the car to the cell having smaller element.

The car stops once it reaches the cell (N, M).

Let us denote the largest element visited by the car by A_{max} and the smallest element as A_{min}. Then, the score of the grid is defined as A_{max} - A_{min}.

Charlie has an array B containing N \cdot M distinct elements. He wants to arrange the elements as a grid of size N\times M such that the score of the grid is minimised.

Help Charlie to construct any such grid.

Note: Please use fast I/O for input and pypy for python submissions.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers N and M — dimensions of the grid A.
- The next line contains N \cdot M distinct elements denoting the array B.

------ Output Format ------ 

For each test case, output N lines each containing M spaced integers denoting the grid A.

If there are multiple possible answers, print any of them.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$2 ≤ N, M ≤ 1000$
$1 ≤ B_{i} ≤ 10^{9}$
- All elements of the array $B$ are distinct.
- Sum of $N \cdot M$ over all test cases do not exceed $10^{6}$.

----- Sample Input 1 ------ 
2
2 2
5 10 20 40
3 2
2 6 4 1 9 20

----- Sample Output 1 ------ 
10 5 
20 40 
2 4 
1 6 
20 9 

----- explanation 1 ------ 
Test case $1$: The car starts from $(1, 1)$. Let us consider the moves based on the grid $[[10, 5], [20, 40]]$.
- In Chef's turn, he will move the car to $(2, 1)$ since $A_{(2, 1)} > A_{(1, 2)}$.
- In Chefina's turn, she will move the car to $(2, 2)$ as it is the only available choice.

Thus, the car covers the elements $[10, 20, 40]$. The largest element in the path is $40$ while the smallest element is $10$. Thus, the score is $40-10 = 30$. It can be shown that this is the minimum possible score that can be achieved in any configuration of grid.

Test case $2$: The car starts from $(1, 1)$. Let us consider the moves based on the grid $[[2, 4], [1, 6], [20, 9]]$.
- In Chef's turn, he will move the car to $(1, 2)$ since $A_{(1, 2)} > A_{(2, 1)}$.
- In Chefina's turn, she will move the car to $(2, 2)$ as it is the only available choice.
- In Chef's turn, he will move the car to $(3, 2)$ as it is the only available choice.

Thus, the car covers the elements $[2, 4, 6, 9]$. The largest element in the path is $9$ while the smallest element is $2$. Thus, the score is $9 - 2 = 7$. It can be shown that this is the minimum possible score that can be achieved in any configuration of grid.

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Constructive algorithms


Solutions:
import sys
t = int(input())
while t:
	(n, m) = map(int, input().split())
	h = n
	p = m
	n = min(h, p)
	m = max(h, p)
	b = [int(x) for x in input().split()]
	b.sort()
	x = min(n, m) - 1
	ch = (x + 1) // 2
	che = x // 2
	ans = sys.maxsize
	pos = -1
	for i in range(ch, n * m - che - n - m + 2):
		j = i + n + m - 2
		if ans > b[j] - b[i]:
			ans = b[j] - b[i]
			pos = i
	mat = [[0 for _ in range(m)] for _ in range(n)]
	if n <= m:
		k = pos
		l = 0
		for i in range(n):
			mat[i][0] = b[k]
			k += 1
		for i in range(1, m):
			mat[n - 1][i] = b[k]
			k += 1
		for i in range(0, n - 1, 2):
			mat[i][1] = b[l]
			l += 1
		for i in range(1, n - 1, 2):
			mat[i][1] = b[k]
			k += 1
		for i in range(0, n - 1):
			for j in range(2, m):
				if l < pos:
					mat[i][j] = b[l]
					l += 1
				else:
					mat[i][j] = b[k]
					k += 1
	else:
		mat = [[0 for _ in range(n)] for _ in range(m)]
		k = pos
		l = 0
		for i in range(m):
			mat[i][0] = b[k]
			k += 1
		for i in range(1, n):
			mat[m - 1][i] = b[k]
			k += 1
		for i in range(0, m - 1, 2):
			mat[i][1] = b[l]
			l += 1
		for i in range(1, m - 1, 2):
			mat[i][1] = b[k]
			k += 1
		for i in range(0, m - 1):
			for j in range(2, n):
				if l < pos:
					mat[i][j] = b[l]
					l += 1
				else:
					mat[i][j] = b[k]
					k += 1
	if h <= p:
		for i in range(n):
			for j in range(m):
				print(mat[i][j], end=' ')
			print()
	else:
		for i in range(m):
			for j in range(n):
				print(mat[j][i], end=' ')
			print()
	t -= 1


for i in range(int(input())):
	(n, m) = map(int, input().split())
	lst = [int(x) for x in input().split()]
	lst.sort()
	(h, p) = (n, m)
	n = min(h, p)
	m = max(h, p)
	x = min(n, m) - 1
	temp = (x + 1) // 2
	t2 = x // 2
	maxv = 999999999999999
	start = -1
	for i in range(temp, n * m - t2 - n - m + 2):
		j = i + n + m - 2
		if maxv > lst[j] - lst[i]:
			maxv = lst[j] - lst[i]
			start = i
	dp = [[0 for j in range(m)] for i in range(n)]
	if n <= m:
		k = start
		l = 0
		for i in range(n):
			dp[i][0] = lst[k]
			k += 1
		for i in range(1, m):
			dp[n - 1][i] = lst[k]
			k += 1
		for i in range(0, n - 1, 2):
			dp[i][1] = lst[l]
			l += 1
		for i in range(1, n - 1, 2):
			dp[i][1] = lst[k]
			k += 1
		for i in range(0, n - 1):
			for j in range(2, m):
				if l < start:
					dp[i][j] = lst[l]
					l += 1
				else:
					dp[i][j] = lst[k]
					k += 1
	if h <= p:
		for i in range(n):
			for j in range(m):
				print(dp[i][j], end=' ')
			print()
	else:
		for i in range(m):
			for j in range(n):
				print(dp[j][i], end=' ')
			print()