Read problem statements in [Mandarin Chinese] and [Vietnamese] as well.

Chef placed $N$ boxes (numbered $1$ through $N$) in a straight line. For each valid $i$, the $i$-th box contains $A_{i}$ balls. 

Then, Chef painted the boxes using $M$ distinct colours in such a way that for each $M$ consecutive boxes, no two of these boxes have the same colour.

Help Chef choose $M$ distinct boxes (not necessarily consecutive) such that no two of the chosen boxes have the same colour and the difference between the number of balls in a box that contains the maximum number of balls and a box that contains the minimum number of balls among the chosen boxes is the smallest possible.

------  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$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the minimum possible difference between the maximum and minimum number of balls in the chosen boxes.

------  Constraints ------
$1 ≤ T ≤ 5$
$2 ≤ M ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$, for each valid $i$

------  Subtasks ------
Subtask #1 (30 points): $N ≤ 10^{3}$

Subtask #2 (70 points): original constraints

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

4 2  

10 20 15 28
----- Sample Output 1 ------ 
5
----- explanation 1 ------ 
Example case 1: Let's denote the colours by 'R' (red) and 'G' (green). There are two possible ways of painting the boxes: "RGRG" and  "GRGR".

There are four ways to choose two boxes (one red and one green box). The numbers of balls in them and the differences are:
- $(10, 28)$ with difference $28-10=18$
- $(10, 20)$ with difference $20-10=10$
- $(15, 28)$ with difference $28-15=13$
- $(15, 20)$ with difference $20-15=5$, which is the smallest possible

Difficulty: HARD
Tags: Sorting

Amortized analysis
Skill types: Sorting

Amortized analysis

Starter code:

Solutions:
for q in range(int(input())):
	(n, m) = map(int, input().split())
	(l1, l, c, f, r, result) = ([int(x) for x in input().split()], [], [0] * m, 0, 0, 10 ** 10)
	for i in range(0, n):
		l2 = []
		(l2.append(l1[i]), l2.append(i % m))
		l.append(l2)
	l.sort()
	for i in range(n):
		while r < n and f < m:
			if c[l[r][1]] == 0:
				f += 1
			c[l[r][1]] += 1
			r += 1
		if f == m:
			result = min(result, l[r - 1][0] - l[i][0])
		c[l[i][1]] -= 1
		if c[l[i][1]] == 0:
			f -= 1
	print(result)


t = int(input())

def minDiff1(a, n, m, w):
	co = [0] * m
	done = [False] * m
	doall = [True] * m
	ca = a[n - 1] - a[0]
	i = 0
	j = 0
	while i < n:
		done[w[i]] = True
		co[w[i]] += 1
		if w[i] == w[j] and i != j:
			co[w[j]] -= 1
			j += 1
		if done == doall:
			while co[w[j]] > 1:
				co[w[j]] -= 1
				j += 1
			ca = min(a[i] - a[j], ca)
			co[w[j]] -= 1
			if co[w[j]] == 0:
				done[w[j]] = False
			j += 1
		i += 1
	print(ca)
for i in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	a = [int(i) for i in input().split()]
	sin = [j[0] for j in sorted(enumerate(a), key=lambda x: x[1])]
	w = [0] * n
	for j in range(n):
		w[j] = sin[j] % m
	a.sort()
	ans = 9147483647
	chk = [int(i) for i in range(m)]
	if m == n:
		print(a[n - 1] - a[0])
	minDiff1(a, n, m, w)


import sys

def smallestDifference(colors, arr):
	color_count = [0] * colors
	arr_with_color = list(zip(arr, [i for i in range(len(arr))]))
	arr_with_color.sort(key=lambda x: x[0])
	(i, j) = (0, 0)
	mini_diff = sys.maxsize
	count = 0
	while i <= len(arr):
		if count < colors and i < len(arr):
			color_count[arr_with_color[i][1] % colors] += 1
			if color_count[arr_with_color[i][1] % colors] == 1:
				count += 1
			i += 1
		elif count >= colors:
			mini_diff = min(mini_diff, arr_with_color[i - 1][0] - arr_with_color[j][0])
			color_count[arr_with_color[j][1] % colors] -= 1
			if color_count[arr_with_color[j][1] % colors] == 0:
				count -= 1
			j += 1
		else:
			break
	return mini_diff
try:
	testcases = int(input())
	for i in range(testcases):
		(arr_len, colors) = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		print(smallestDifference(colors, arr))
except:
	pass


for x in range(int(input())):
	(m, n) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	l2 = []
	l3 = [0] * n
	t = 0
	flagi = 0
	for x in range(len(l)):
		l1.append([l[x], x % n])
	l1.sort()
	count = 0
	for y in range(m):
		if count != n:
			if l3[l1[y][1]] == 0:
				k = 0
				if flagi != 1:
					k = y
					flagi = 1
				l3[l1[y][1]] += 1
				count += 1
				if count == n:
					t = y + 1
					l2.append(abs(l1[y][0] - l1[k][0]))
					break
			else:
				l3[l1[y][1]] += 1
	for x in range(m - n):
		l3[l1[x][1]] -= 1
		flag = 0
		if l3[l1[x][1]] == 0:
			for y in range(t, m):
				if l1[y][1] == l1[x][1]:
					l3[l1[y][1]] += 1
					t = y + 1
					l2.append(abs(l1[y][0] - l1[x + 1][0]))
					flag = 1
					break
				else:
					l3[l1[y][1]] += 1
			if flag == 0:
				break
		else:
			l2.append(abs(l1[t - 1][0] - l1[x + 1][0]))
	print(min(l2))


import heapq

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	cl = []
	for i in range(len(l)):
		cl.append((i + 1) % m)
	cl = sort_list(cl, l)
	l.sort()
	di = {}
	i = len(l) - 1
	while i >= 0:
		co = cl[i]
		val = l[i]
		if co in di:
			li = di[co]
			li.append(val)
		else:
			di[co] = [val]
		i = i - 1
	min_heap = []
	max_heap = []
	for i in range(m):
		v = di[i]
		vf = v[-1]
		min_heap.append(vf)
		max_heap.append(-1 * vf)
	heapq.heapify(min_heap)
	heapq.heapify(max_heap)
	midi = {}
	f = 0
	i = 0
	while i < len(l) and f == 0:
		if i == 0:
			prev = cl[i]
			val1 = di[prev]
			if len(val1) == 0:
				f = 1
			else:
				mi = min_heap[0]
				ma = max_heap[0]
				ma = -1 * ma
				diff = abs(ma - mi)
				valu = val1[-1]
				val1.pop()
				if valu in midi:
					gf = midi[valu]
					midi[valu] = gf + 1
				else:
					midi[valu] = 1
			di[prev] = val1
		else:
			val2 = di[prev]
			if len(val2) == 0:
				f = 1
			else:
				chk = val2[-1]
				heapq.heappush(min_heap, chk)
				heapq.heappush(max_heap, -1 * chk)
				mival = min_heap[0]
				if mival in midi:
					if midi[mival] > 0:
						heapq.heappop(min_heap)
						fr = midi[mival]
						fr = fr - 1
						midi[mival] = fr
				maxv = max_heap[0]
				minv = min_heap[0]
				maxv = -1 * maxv
				diff2 = abs(maxv - minv)
				if diff2 < diff:
					diff = diff2
				prev = cl[i]
				val1 = di[prev]
				if len(val1) == 0:
					f = 1
				else:
					valu = val1[-1]
					val1.pop()
					if valu in midi:
						gf = midi[valu]
						midi[valu] = gf + 1
					else:
						midi[valu] = 1
				di[prev] = val1
		i = i + 1
	print(diff)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	final = []
	final = [j % m for j in sorted([i for i in range(n)], key=lambda x: a[x])]
	a.sort()
	found = {}
	i = 0
	j = 0
	ans = a[-1] - a[0]
	while i < n - m + 1 and j < n:
		while j < n and len(found.keys()) < m:
			if final[j] in found:
				found[final[j]] += 1
			else:
				found[final[j]] = 1
			j += 1
		while i < n - m + 1 and len(found.keys()) == m:
			ans = min(ans, a[j - 1] - a[i])
			found[final[i]] -= 1
			if found[final[i]] == 0:
				del found[final[i]]
			i += 1
	print(ans)


from heapq import *
import itertools, math, heapq

def handle_input(M, N, A):
	heap = []
	lists = [sorted(A[i::M]) for i in range(M)]
	curr_max = 0
	for i in range(M):
		item = lists[i][0]
		heapq.heappush(heap, (item, i))
		if item > curr_max:
			curr_max = item
	min_diff = float('inf')
	indexes = [0 for i in range(M)]
	min_item = float('inf')
	while True:
		(min_item, i) = heapq.heappop(heap)
		diff = curr_max - min_item
		if diff < min_diff:
			min_diff = diff
		indexes[i] += 1
		try:
			item = lists[i][indexes[i]]
		except:
			break
		if item > curr_max:
			curr_max = item
		heapq.heappush(heap, (item, i))
	print(min_diff)
T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	handle_input(M, N, A)


from sys import stdin
from heapq import heapify, heappop, heappush
t = int(stdin.readline())
while t:
	(n, m) = [int(x) for x in stdin.readline().split()]
	a = [(x, int(y)) for (x, y) in enumerate(stdin.readline().split())]
	a.sort(key=lambda x: x[1])
	seg_all_col = [[] for x in range(m)]
	for i in range(n):
		seg_all_col[a[i][0] % m].append(a[i][1])
	vis = [[1, len(i)] for i in seg_all_col]
	(mn, mx) = (float('inf'), float('-inf'))
	li = []
	for i in range(m):
		mx = max(mx, seg_all_col[i][0])
		li.append([seg_all_col[i][0], i])
	curMinRange = float('inf')
	heapify(li)
	temp = []
	while True:
		temp = heappop(li)
		mn = temp[0]
		curMinRange = min(curMinRange, mx - mn)
		if vis[temp[1]][0] == vis[temp[1]][1]:
			break
		else:
			nxt = seg_all_col[temp[1]][vis[temp[1]][0]]
			mx = max(mx, nxt)
			vis[temp[1]][0] += 1
			heappush(li, [nxt, temp[1]])
	print(curMinRange)
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	colors = list(range(m)) * (n // m) + list(range(n % m))
	a = sorted([[x, y] for (x, y) in zip(a, colors)])
	color_slots = [None] * m
	min_arr = []
	min_ind = 0
	c_cnt = 0
	res = 10 ** 9 + 10
	for (val, color) in a:
		min_arr.append(val)
		if color_slots[color] is None:
			c_cnt += 1
		else:
			min_arr[color_slots[color]] = None
		color_slots[color] = len(min_arr) - 1
		if c_cnt == m:
			mx = min_arr[-1]
			while min_arr[min_ind] is None:
				min_ind += 1
			mn = min_arr[min_ind]
			res = min(res, mx - mn)
	print(res)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	func = lambda x: (int(x[1]), x[0] % m)
	arr = list(map(func, enumerate(input().split())))
	arr.sort()
	cnt = [0] * m
	cnt0 = m
	r = 0
	ans = float('inf')
	for l in range(n):
		while r < n and cnt0 > 0:
			cnt0 -= cnt[arr[r][1]] == 0
			cnt[arr[r][1]] += 1
			r += 1
		if cnt0 == 0:
			ans = min(ans, arr[r - 1][0] - arr[l][0])
		cnt[arr[l][1]] -= 1
		cnt0 += cnt[arr[l][1]] == 0
	print(ans)


from heapq import heappush, heappop, heapify

def choose(buckets, n, m):
	chosen = [(buckets[i][0], i, 0) for i in range(m)]
	heapify(chosen)
	max_box = max(chosen)[0]
	ans = float('inf')
	while chosen:
		ans = min(ans, max_box - chosen[0][0])
		(cur_box, i, idx) = heappop(chosen)
		cur_bucket = buckets[i]
		if idx + 1 >= len(cur_bucket):
			break
		next_box = cur_bucket[idx + 1]
		heappush(chosen, (next_box, i, idx + 1))
		max_box = max(max_box, next_box)
	return ans
try:
	test_num = int(input())
	get_input = lambda : list(map(int, input().split()))
	for _ in range(test_num):
		(n, m) = get_input()
		boxes = get_input()
		buckets = [[] for i in range(m)]
		for (i, num) in enumerate(boxes):
			buckets[i % m] += [num]
		for bucket in buckets:
			bucket.sort()
		print(choose(buckets, n, m))
except EOFError:
	pass


t = int(input())

def sortSecond(val):
	return val[1]

def minDiff(arr, N, K, w, chk, res):
	wa = res
	for i in range(N - K + 1):
		curSeqDiff = arr[i + K - 1] - arr[i]
		if curSeqDiff < res:
			yes = set(chk).issubset(set(w[i:i + K]))
		if curSeqDiff < res and yes:
			res = curSeqDiff
		elif curSeqDiff < res and ~yes:
			wa = curSeqDiff
	return (res, wa)

def sol(a, n, m, w, chk, ans):
	(ca, wa) = minDiff(a, n, m, w, chk, ans)
	while wa < ca:
		(c1, wa) = minDiff(a, n, m + 1, w, chk, ca)
		if c1 < ca:
			ca = c1
		if m >= n:
			break
		m += 1
	print(ca)

def minDiff1(a, n, m, w):
	co = [0] * m
	done = [False] * m
	doall = [True] * m
	ca = a[n - 1] - a[0]
	i = 0
	j = 0
	while i < n:
		done[w[i]] = True
		co[w[i]] += 1
		if w[i] == w[j] and i != j:
			co[w[j]] -= 1
			j += 1
		if done == doall:
			while co[w[j]] > 1:
				co[w[j]] -= 1
				j += 1
			ca = min(a[i] - a[j], ca)
			co[w[j]] -= 1
			if co[w[j]] == 0:
				done[w[j]] = False
			j += 1
		i += 1
	print(ca)
for i in range(t):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	a = [int(i) for i in input().split()]
	sin = [j[0] for j in sorted(enumerate(a), key=lambda x: x[1])]
	w = [0] * n
	for j in range(n):
		w[j] = sin[j] % m
	a.sort()
	ans = 9147483647
	chk = [int(i) for i in range(m)]
	if m == n:
		print(a[n - 1] - a[0])
	minDiff1(a, n, m, w)


import heapq
test = int(input())

def findMaximumElement(heap):
	maximumElement = heap[0]
	for i in range(1, len(heap)):
		maximumElement = max(maximumElement, heap[i])
	return maximumElement
while test > 0:
	test -= 1
	(n, m) = map(int, input().split())
	mat = [[] for i in range(m)]
	arr = list(map(int, input().split()))
	for i in range(len(arr)):
		mat[i % m].append(arr[i])
	for i in range(len(mat)):
		mat[i].sort()
	minheap = []
	for i in range(len(mat)):
		minheap.append([mat[i][0], i, 0])
	heapq.heapify(minheap)
	mindiff = 10 ** 10
	b = findMaximumElement(minheap)
	while True:
		a = heapq.heappop(minheap)
		diff = b[0] - a[0]
		if diff < mindiff:
			mindiff = diff
		k = a[2] + 1
		if k > len(mat[a[1]]) - 1:
			break
		heapq.heappush(minheap, [mat[a[1]][a[2] + 1], a[1], a[2] + 1])
		if mat[a[1]][a[2] + 1] > b[0]:
			b = [mat[a[1]][a[2] + 1], a[1], a[2] + 1]
	print(mindiff)


from bisect import insort
for t in range(int(input())):
	(n, m) = map(int, input().split())
	li = list(map(int, input().split()))
	li2 = [[] for i in range(m)]
	for x in range(n):
		insort(li2[x % m], li[x])
	val = [[li2[x][0], x] for x in range(m)]
	val.sort()
	pt = [0] * m
	m_x = val[-1][0]
	m_n = val[0][0]
	res = m_x - m_n
	while res:
		res = min(m_x - m_n, res)
		ind = val[0][1]
		try:
			pt[ind] += 1
			del val[0]
			insort(val, [li2[ind][pt[ind]], ind])
			m_x = max(m_x, val[-1][0])
		except:
			break
		m_n = val[0][0]
	print(res)


import bisect as b
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	for i in range(n):
		l[i] = [l[i], i % m]
	l.sort()
	ans = []
	d = {}
	min1 = 2 ** 32
	for i in l:
		if d.get(i[1], -1) == -1:
			d[i[1]] = i[0]
			ans.append(i[0])
		else:
			val = d[i[1]]
			ind = b.bisect(ans, val)
			del ans[ind - 1]
			ans.append(i[0])
			d[i[1]] = i[0]
		if len(ans) == m:
			min1 = min(ans[-1] - ans[0], min1)
	print(min(ans[-1] - ans[0], min1))


for tc in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = []
	temp = []
	for i in range(m):
		for j in range(i, n, m):
			temp.append((a[j], i))
	temp = sorted(temp, key=lambda x: x[0])
	start = 0
	finish = 1
	res = 10 ** 10
	dic = {}
	for i in range(m):
		dic[i] = 0
	li = [temp[start][1]]
	dic[temp[start][1]] = 1
	flag = 0
	for i in range(finish, n):
		dic[temp[i][1]] += 1
		if flag == 0 and li.count(temp[i][1]) == 0:
			li.append(temp[i][1])
			finish = i
		if flag == 0 and len(li) == m:
			flag = 1
			x = abs(temp[start][0] - temp[finish][0])
			if x < res:
				res = x
			start += 1
			dic[temp[start - 1][1]] -= 1
		if flag == 1:
			finish = i
			while 1:
				if dic[temp[start - 1][1]] == 0:
					break
				else:
					x = abs(temp[start][0] - temp[finish][0])
					if x < res:
						res = x
					start += 1
					dic[temp[start - 1][1]] -= 1
	print(res)


from bisect import insort
for t in range(int(input())):
	(n, m) = map(int, input().split())
	li = list(map(int, input().split()))
	li2 = [[] for i in range(m)]
	for x in range(n):
		insort(li2[x % m], li[x])
	val = [[li2[x][0], x] for x in range(m)]
	val.sort()
	pt = [0] * m
	mx = val[-1][0]
	mn = val[0][0]
	result = mx - mn
	while result:
		result = min(mx - mn, result)
		ind = val[0][1]
		try:
			pt[ind] += 1
			del val[0]
			insort(val, [li2[ind][pt[ind]], ind])
			mx = max(mx, val[-1][0])
		except:
			break
		mn = val[0][0]
	print(result)


t = int(input())
for q in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append((a[i], i % m))
	l.sort()
	visit = [0] * m
	m_l = [0] * m
	c = 0
	for i in range(n):
		max_ = l[i][0]
		if visit[l[i][1]] == 0:
			c += 1
			visit[l[i][1]] = 1
		m_l[l[i][1]] = l[i][0]
		if c == m:
			min_ = min(m_l)
			res = max_ - min_
			break
	i += 1
	while i < n:
		y = m_l[l[i][1]]
		max_ = l[i][0]
		m_l[l[i][1]] = l[i][0]
		if y == min_:
			min_ = min(m_l)
			res = min(res, max_ - min_)
		i += 1
	print(res)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = [int(v) for v in input().split()]
	s = [[0 for j in range(2)] for i in range(n)]
	k = 0
	for j in range(n):
		s[j][0] = a[j]
		s[j][1] = k
		k = k + 1
		if k == m:
			k = 0
	s.sort()
	v = {}
	start = 0
	k = m
	res = s[n - 1][0] - s[0][0]
	for j in range(n):
		if s[j][1] in v:
			v[s[j][1]] = v[s[j][1]] + 1
		else:
			v[s[j][1]] = 1
		while len(v) == k:
			an = s[j][0] - s[start][0]
			if an < res:
				res = an
			if s[start][1] in v:
				if v[s[start][1]] == 1:
					del v[s[start][1]]
					start = start + 1
				else:
					v[s[start][1]] = v[s[start][1]] - 1
					start = start + 1
	print(res)


def solve(l):
	mi = [float('inf'), -1]
	ma = 0
	for i in range(len(l)):
		if l[i] < mi[0]:
			mi[0] = l[i]
			mi[1] = i
		if l[i] > ma:
			ma = l[i]
	return (ma - mi[0], mi[1])
for t in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	a = [(int(j), i % m) for (i, j) in enumerate(input().split())]
	a.sort()
	l = [None for i in range(m)]
	last = 0
	index = []
	diff = float('inf')
	sel = 0
	all_sel = 2 ** m - 1
	for i in range(n):
		l[a[i][1]] = a[i][0]
		last = a[i][0]
		sel = sel | 1 << a[i][1]
		index.append(a[i][1])
		if sel == all_sel:
			(d, val) = solve(l)
			sel = sel & ~(1 << val)
			diff = min(diff, d)
	print(diff)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	k = list(map(int, input().split()))
	s = [0] * n
	j = 0
	v = [0] * m
	while j != n:
		for i in range(m):
			s[j] = i
			j += 1
			if j >= n:
				break
	z = [x for (_, x) in sorted(zip(k, s))]
	h = sorted(k)
	c = 0
	a = 0
	minn = 100000000000000
	for i in range(n):
		if v[z[i]] == 0:
			c += 1
		v[z[i]] += 1
		if c == m:
			while c >= m:
				temp = abs(h[a] - h[i])
				if minn > temp:
					minn = temp
				v[z[a]] -= 1
				if v[z[a]] != 0:
					a += 1
				else:
					c -= 1
					a += 1
	print(minn)


def try3(n, m, pts_s):
	i = 0
	mi = 10 ** 10
	res = [-1] * m
	tmp = m
	mi_i = -1
	while i < n - m - 1:
		if tmp == 0:
			mi = min(mi, res[pts_s[i - 1][1]] - min(res))
			if mi == 0:
				break
		if res[pts_s[i][1]] == -1:
			tmp -= 1
		res[pts_s[i][1]] = pts_s[i][0]
		i += 1
	print(mi)

def try2():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		k = 0
		pts = []
		for i in input().split():
			pts.append([int(i), k % m])
			k += 1
		pts_s = sorted(pts)
		if m == n:
			print(pts_s[-1][0] - pts_s[0][0])
			continue
		if n > 1000:
			try3(n, m, pts_s)
			continue
		i = 0
		mi = 10 ** 10
		while i < n - m:
			ct = [0] * m
			tmp = m
			for j in range(i, n):
				if ct[pts_s[j][1]] == 0:
					tmp -= 1
					ct[pts_s[j][1]] = 1
				if tmp == 0:
					mi = min(mi, pts_s[j][0] - pts_s[i][0])
					break
			i += 1
			if tmp == 0:
				mi = min(mi, pts_s[-1][0] - pts_s[i - 1][0])
			if mi == 0:
				break
		print(mi)

def try1():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		a = [int(i) for i in input().split()]
		ar1 = []
		if m == n:
			print(max(a) - min(a))
			continue
		mi_v = 10 ** 8
		mi_i = 0
		kk = 0
		for i in range(0, n, m):
			ar1.append(a[i:i + m])
			tp = max(ar1[kk]) - min(ar1[kk])
			if mi_v > tp and len(ar1[kk]) == m:
				mi_v = tp
				mi_i = kk
			kk += 1
		res = ar1[mi_i]
		mi = min(res)
		ma = max(res)
		for i in range(len(ar1)):
			if i == kk:
				continue
			for j in range(min(len(res), len(ar1[i]))):
				if ar1[i][j] >= mi and ar1[i][j] <= ma:
					res[j] = ar1[i][j]
					mi = min(res)
					ma = max(res)
		print(max(res) - min(res))
try2()


t = int(input())
for itr in range(t):
	nm = input().split(' ')
	(n, m) = (int(nm[0]), int(nm[1]))
	a = list(map(int, input().split(' ')))
	collis = {}
	aa = [[a[i], i % m] for i in range(n)]
	aa.sort(reverse=True)
	mini = 1000000000
	i = 0
	while len(collis.keys()) < m:
		if collis.get(aa[i][1]) is None:
			collis[aa[i][1]] = 1
		else:
			collis[aa[i][1]] += 1
		i += 1
	j = 0
	i -= 1
	while j < n:
		if aa[j][0] - aa[i][0] < mini:
			mini = aa[j][0] - aa[i][0]
		fl = False
		temp = aa[j][0]
		while j < n and aa[j][0] == temp:
			if collis.get(aa[j][1]) is not None:
				collis[aa[j][1]] -= 1
				if collis[aa[j][1]] == 0:
					del collis[aa[j][1]]
			j += 1
		if j >= n:
			break
		i = max(i + 1, j)
		flag = False
		while len(collis.keys()) < m:
			if i == n:
				flag = True
				break
			if collis.get(aa[i][1]) is None:
				collis[aa[i][1]] = 1
			else:
				collis[aa[i][1]] += 1
			i += 1
		if flag:
			break
		i -= 1
	print(mini)


def main():
	from heapq import _heapify_max, heapify, heappop, heappush, _heappop_max
	t = int(input().strip())
	for _ in range(t):
		(n, m) = map(int, input().strip().split())
		a = list(map(int, input().strip().split()))
		mlst = []
		mxhp = []
		mnhp = []
		cd = 0
		for l in range(m):
			i = l
			ls = []
			while i < n:
				ls.append(a[i])
				i += m
			ls.sort(key=lambda x: -x)
			mxhp.append((-1 * ls[-1], l))
			mnhp.append((ls[-1], l))
			mlst.append(ls)
		heapify(mxhp)
		heapify(mnhp)
		(mn, x) = heappop(mnhp)
		(mx, y) = mxhp[0]
		cd = -1 * mx - mn
		mxhp.pop()
		while len(mlst[x]) > 0:
			mlst[x].pop()
			if len(mlst[x]) == 0:
				break
			nx = mlst[x][-1]
			heappush(mxhp, (-1 * nx, x))
			heappush(mnhp, (nx, x))
			(mn, x) = heappop(mnhp)
			(mx, y) = mxhp[0]
			d = -1 * mx - mn
			if d < cd:
				cd = d
			mxhp.pop()
		print(cd)
main()


from collections import defaultdict
from heapq import *
import itertools, math, heapq

def parse_integer_list():
	return [int(x) for x in input().split()]

def handle_input(M, N, A):
	heap = []
	N = len(A)
	num_of_lists = M
	lists = [list() for i in range(num_of_lists)]
	for i in range(N):
		lists[i % num_of_lists].append(A[i])
	for l in lists:
		l.sort()
	curr_max = 0
	for i in range(num_of_lists):
		item = lists[i][0]
		heapq.heappush(heap, (item, i))
		if item > curr_max:
			curr_max = item
	min_diff = float('inf')
	indexes = [0 for i in range(num_of_lists)]
	min_item = float('inf')
	while True:
		(min_item, i) = heapq.heappop(heap)
		diff = curr_max - min_item
		if diff < min_diff:
			min_diff = diff
		indexes[i] += 1
		try:
			item = lists[i][indexes[i]]
		except:
			break
		if item > curr_max:
			curr_max = item
		heapq.heappush(heap, (item, i))
	print(min_diff)
T = int(input())
for i in range(T):
	(N, M) = parse_integer_list()
	A = parse_integer_list()
	handle_input(M, N, A)


import sys
import heapq
t = int(input())
for q in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	color_sets = []
	for i in range(k):
		color_set = []
		j = i
		while j < n:
			color_set.append(arr[j])
			j += k
		color_set.sort()
		color_sets.append(color_set)
	min_diff = sys.maxsize
	min_heap = []
	max_value = 0
	for i in range(k):
		max_value = max(max_value, color_sets[i][0])
		heapq.heappush(min_heap, (color_sets[i][0], i))
		del color_sets[i][0]
	i = 0
	while i < 5:
		(min_value, index) = heapq.heappop(min_heap)
		min_diff = min(min_diff, max_value - min_value)
		if len(color_sets[index]) == 0:
			break
		heapq.heappush(min_heap, (color_sets[index][0], index))
		if color_sets[index][0] > max_value:
			max_value = color_sets[index][0]
		del color_sets[index][0]
	print(min_diff)


import heapq
testCase = int(input())
for t in range(testCase):
	(n, m) = [int(x) for x in input().split()]
	arrayBalls = [int(x) for x in input().split()]
	listMBalls = []
	for (index, x) in enumerate(arrayBalls):
		if len(listMBalls) > index % m:
			listMBalls[index % m].append(x)
		else:
			arr = []
			arr.append(x)
			listMBalls.append(arr)
	heap = []
	for x in listMBalls:
		x.sort()
	maxVal = (0, 0, 0)
	for (index, x) in enumerate(listMBalls):
		heap.append((x[0], index, 0))
		if x[0] > maxVal[0]:
			maxVal = (x[0], index, 0)
	heapq.heapify(heap)
	diff = maxVal[0]
	while len(heap) > 0:
		x = heapq.heappop(heap)
		if maxVal[0] - x[0] < diff:
			diff = maxVal[0] - x[0]
		tup = ()
		if len(listMBalls[x[1]]) > x[2] + 1:
			tup = (listMBalls[x[1]][x[2] + 1], x[1], x[2] + 1)
		else:
			break
		heapq.heappush(heap, tup)
		if tup[0] > maxVal[0]:
			maxVal = tup
	print(diff)


from itertools import combinations
import sys

def a_le():
	return list(map(int, sys.stdin.readline().strip().split()))

def int_le():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	A = a_le()
	B = []
	if N == M:
		print(max(A) - min(A))
	else:
		for i in range(len(A)):
			j = i % M + 1
			B.append([A[i], j])
		B.sort()
		C = [0] * M
		count = 0
		Res = []
		for (i, j) in B:
			if count < M:
				if C[j - 1] == 0:
					count += 1
				C[j - 1] = i
				if 0 not in C:
					count -= 1
					Res.append(max(C) - min(C))
					C[C.index(min(C))] = 0
		print(min(Res))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	my_list = list(map(int, input().split()))
	my_list_2 = list(set(my_list))
	my_dict = {}
	for i in my_list_2:
		my_dict[i] = []
	for i in range(n):
		jk = i % m
		my_dict[my_list[i]].append(jk)
	s = 99 ** 99
	s1 = 99 ** 99
	my_list_2 = list(my_dict.keys())
	my_list_2.sort(reverse=True)
	j = -1
	n = []
	c = [0] * m
	my_dif_c = 0
	for i in range(len(my_list_2)):
		while j + 1 < len(my_list_2) and my_dif_c != m:
			j = j + 1
			for k in my_dict[my_list_2[j]]:
				if c[k] == 0:
					my_dif_c += 1
				c[k] += 1
			if my_dif_c == m:
				f = 1
				break
		if my_dif_c == m:
			s1 = abs(my_list_2[i] - my_list_2[j])
			s = min(s, s1)
		for k in my_dict[my_list_2[i]]:
			c[k] -= 1
			if c[k] == 0:
				my_dif_c -= 1
	print(s)


import sys
import heapq

def getInput(num):
	if num:
		inputArr = input().split()
		if len(inputArr) != num:
			print(f'The length is {len(inputArr)} not same as asked for {num}')
			sys.exit(0)
		for i in range(0, len(inputArr)):
			inputArr[i] = int(inputArr[i])
		return inputArr
	elif num == 0:
		return int(input())
	elif num == None:
		inputArr = input().split()
		for i in range(0, len(inputArr)):
			inputArr[i] = int(inputArr[i])
		return inputArr
for test in range(0, getInput(0)):
	(N, M) = getInput(2)
	numList = getInput(N)
	myArr = []
	for i in range(0, M):
		myArr.append([])
	for i in range(0, N):
		myArr[i % M].append(numList[i])
	for i in range(0, M):
		myArr[i].sort()
	heap = []
	myMax = 0
	myDiff = 4294967295
	for i in range(0, M):
		myTempVal0 = (myArr[i].pop(0) << 32) + i
		if myMax < myTempVal0:
			myMax = myTempVal0
		heapq.heappush(heap, myTempVal0)
	while True:
		myVal0 = heap[0]
		index = myVal0 & 4294967295
		currDiff = (myMax >> 32) - (myVal0 >> 32)
		if currDiff < myDiff:
			myDiff = currDiff
		if len(myArr[index]) == 0:
			break
		else:
			val0 = (myArr[index].pop(0) << 32) + index
			if val0 > myMax:
				myMax = val0
			heapq.heapreplace(heap, val0)
	print(myDiff)


import heapq
import math

class min_heap_obj:

	def __init__(self, value, index_of_b, index_in_b, len_b, connection):
		self.value = value
		self.index_of_b = index_of_b
		self.index_in_b = index_in_b
		self.len_b = len_b
		self.connection = connection

	def __lt__(self, other):
		return self.value < other.value

class max_heap_obj:

	def __init__(self, value, index_in_heap):
		self.value = value
		self.index_in_heap = index_in_heap

	def __lt__(self, other):
		return self.value < other.value

def update_min_heap(min_heap, len_heap):
	m = len_heap
	index = 0
	while True:
		child_present = False
		c1 = False
		if index * 2 + 1 < m:
			child = min_heap[index * 2 + 1]
			child_index = index * 2 + 1
			child_present = True
		if index * 2 + 2 < m:
			if min_heap[index * 2 + 2] < child:
				child = min_heap[index * 2 + 2]
				child_index = index * 2 + 2
		if child_present:
			if min_heap[index] > child:
				(min_heap[index], min_heap[child_index]) = (child, min_heap[index])
				index = child_index
				c1 = True
		if not child_present:
			break
		elif not c1:
			break

def update_max_heap(max_heap, target, len_heap):
	m = len_heap
	index = target
	while True:
		child_present = False
		c1 = False
		if index * 2 + 1 < m:
			child = max_heap[index * 2 + 1]
			child_index = index * 2 + 1
			child_present = True
		if index * 2 + 2 < m:
			if max_heap[index * 2 + 2] > child:
				child = max_heap[index * 2 + 2]
				child_index = index * 2 + 2
		if child_present:
			if max_heap[index] < child:
				(max_heap[index], max_heap[child_index]) = (child, max_heap[index])
				max_heap[index].index_in_heap = index
				max_heap[child_index].index_in_heap = child_index
				index = child_index
				c1 = True
		if not child_present:
			break
		elif not c1:
			break
	while True:
		c1 = False
		if index == 0:
			break
		if max_heap[index] > max_heap[(index - 1) // 2]:
			(max_heap[index], max_heap[(index - 1) // 2]) = (max_heap[(index - 1) // 2], max_heap[index])
			max_heap[index].index_in_heap = index
			max_heap[(index - 1) // 2].index_in_heap = (index - 1) // 2
			index = (index - 1) // 2
			c1 = True
		if not c1:
			break
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = []
	for i in range(m):
		temp = []
		for j in range(i, n, m):
			temp.append(a[j])
		b.append(sorted(temp))
	temp = []
	temp2 = []
	for i in range(m):
		temp2.append(max_heap_obj(b[i][0], 'ok'))
	for i in range(m):
		temp.append(min_heap_obj(b[i][0], i, 0, len(b[i]), 'temp_obj_max'))
	for i in range(m):
		temp[i].connection = temp2[i]
	heapq.heapify(temp)
	heapq._heapify_max(temp2)
	for i in range(m):
		temp2[i].index_in_heap = i
	ans = temp2[0].value - temp[0].value
	while True:
		temp[0].index_in_b += 1
		if temp[0].index_in_b == temp[0].len_b:
			break
		temp[0].value = b[temp[0].index_of_b][temp[0].index_in_b]
		temp[0].connection.value = temp[0].value
		target = temp[0].connection.index_in_heap
		update_min_heap(temp, m)
		update_max_heap(temp2, target, m)
		if temp2[0].value - temp[0].value < ans:
			ans = temp2[0].value - temp[0].value
	print(ans)


def findsub(string, pat):
	len1 = len(string)
	len2 = len(pat)
	hash_pat = [0] * (10 ** 5 + 1)
	hash_str = [0] * (10 ** 5 + 1)
	for i in range(0, len2):
		hash_pat[pat[i]] += 1
	mindif = 10 ** 10
	(start, start_index, min_len) = (0, -1, float('inf'))
	count = 0
	for j in range(0, len1):
		hash_str[string[j][1]] += 1
		if hash_pat[string[j][1]] != 0 and hash_str[string[j][1]] <= hash_pat[string[j][1]]:
			count += 1
		if count == len2:
			while hash_str[string[start][1]] > hash_pat[string[start][1]] or hash_pat[string[start][1]] == 0:
				if hash_str[string[start][1]] > hash_pat[string[start][1]]:
					hash_str[string[start][1]] -= 1
				start += 1
			len_window = j - start + 1
			tmp = string[j][0] - string[start][0]
			mindif = min(mindif, tmp)
	return mindif
for ii in range(int(input())):
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	k = [i for i in range(0, m)]
	cnt = 1
	s = []
	for i in p:
		s.append([i, cnt])
		cnt = (cnt + 1) % m
	s.sort()
	a = findsub(s, k)
	print(a)


def sortSecond(val):
	return val[0]
for T in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	temp = []
	for i in range(n):
		temp.append([l[i], i % m])
	temp.sort(key=sortSecond)
	temp1 = [0] * m
	st = 0
	for i in range(n):
		temp1[temp[i][1]] += 1
		if not 0 in temp1:
			end = i
			break
	dif = temp[end][0] - temp[st][0]
	while end < n:
		if not 0 in temp1:
			if temp[end][0] - temp[st][0] < dif:
				dif = temp[end][0] - temp[st][0]
			temp1[temp[st][1]] -= 1
			st += 1
		else:
			end += 1
			if end == n:
				break
			temp1[temp[end][1]] += 1
	print(dif)


import heapq
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(input().split())
	a = []
	for i in range(n):
		a.append(int(l[i]))
	ans = []
	for i in range(m):
		x = []
		ans.append(x)
	for i in range(n):
		ans[i % m].append(a[i])
	ptr = []
	for i in range(m):
		ans[i].sort()
		ptr.append(0)
	min_range = 10000000000
	minind = 0
	curr = []
	maxi = 0
	for i in range(m):
		temp = []
		temp.append(ans[i][0])
		temp.append(0)
		temp.append(i)
		curr.append(temp)
		if ans[i][0] > maxi:
			maxi = ans[i][0]
	heapq.heapify(curr)
	while 1:
		mini = heapq.heappop(curr)
		if maxi - mini[0] < min_range:
			min_range = maxi - mini[0]
		if mini[1] + 1 == len(ans[mini[2]]):
			break
		temp = []
		temp.append(ans[mini[2]][mini[1] + 1])
		temp.append(mini[1] + 1)
		temp.append(mini[2])
		heapq.heappush(curr, temp)
		if ans[mini[2]][mini[1] + 1] > maxi:
			maxi = ans[mini[2]][mini[1] + 1]
	print(min_range)


t = int(input())
for _ in range(t):
	(length, m) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = [0] * m
	answer = 10000000000
	res = [[0, 0] for i in range(length)]
	lookup = [0] * m
	for i in range(length):
		res[i][0] = a[i]
		res[i][1] = i % m
	res = sorted(res)
	for i in range(length):
		maxi = res[i][0]
		index = res[i][1]
		removed = ans[index]
		ans[index] = res[i][0]
		lookup.remove(removed)
		lookup.append(res[i][0])
		mini = lookup[0]
		if mini != 0:
			answer = min(answer, maxi - mini)
	print(answer)


import math
import time
testcases = int(input())
for testcase in range(testcases):
	(n, m) = map(int, input().split())
	b = list(map(int, input().split()))
	boxes_dict = {}
	class_val = 0
	for box in b:
		if boxes_dict.get(box):
			boxes_dict[box].append(class_val)
		else:
			boxes_dict[box] = [class_val]
		class_val = (class_val + 1) % m
	boxes = []
	vals = sorted(boxes_dict.keys())
	for val in vals:
		boxes.append((val, boxes_dict[val]))
	counts = [0] * m
	alive = 0
	(l, r) = (0, 0)
	result = math.inf
	k = len(boxes)
	while l <= r and r < k:
		while l <= r and r < k and (alive != m):
			classes = boxes[r][1]
			for c in classes:
				counts[c] += 1
				if counts[c] == 1:
					alive += 1
			if alive == m:
				dist = boxes[r][0] - boxes[l][0]
				result = min(result, dist)
				break
			r += 1
		while l <= r and alive == m:
			if alive == m:
				dist = boxes[r][0] - boxes[l][0]
				result = min(result, dist)
			classes = boxes[l][1]
			for c in classes:
				counts[c] -= 1
				if counts[c] == 0:
					alive -= 1
			l += 1
		r += 1
	print(result)


for _ in range(int(input().strip())):
	(n, m) = [int(i) for i in input().strip().split()]
	old_boxes = [(int(inp), i % m) for (i, inp) in enumerate(input().strip().split())]
	old_boxes.sort()
	old_boxes.append((0, m))
	first = 0
	boxes = []
	for i in range(1, n + 1):
		if old_boxes[first][1] != old_boxes[i][1]:
			boxes.append((old_boxes[first][0], old_boxes[i - 1][0], old_boxes[first][1]))
			first = i
	cnt_colors = [0 for _ in range(m)]
	unselected_colors = {i for i in range(m)}
	first = 0
	mini = 10 ** 10
	cnt_colors[boxes[first][2]] += 1
	unselected_colors -= {boxes[first][2]}
	for i in range(1, len(boxes)):
		cnt_colors[boxes[i][2]] += 1
		unselected_colors -= {boxes[i][2]}
		while not unselected_colors:
			ball_cnt = boxes[i][0] - boxes[first][1]
			if ball_cnt < mini:
				mini = ball_cnt
			cnt_colors[boxes[first][2]] -= 1
			if not cnt_colors[boxes[first][2]]:
				unselected_colors.add(boxes[first][2])
			first += 1
	print(mini)


import heapq

class ball:

	def __init__(self, value, index, index2):
		self.value = value
		self.index = index
		self.index2 = index2

	def __lt__(self, other):
		return self.value < other.value

def update_min(arr, a, mini, maxi, mini_index):
	i = arr[0].index2
	if i != len(a[mini_index]) - 1:
		i += 1
		if a[mini_index][i] > maxi[0]:
			maxi[0] = a[mini_index][i]
		while i < len(a[mini_index]) - 1 and a[mini_index][i + 1] < maxi[0]:
			i += 1
		heapq.heapreplace(arr, ball(a[mini_index][i], mini_index, i))
		return True
	return False
for t in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	x = [int(i) for i in input().split()]
	a = [[] for i in range(m)]
	i = 0
	while i < n:
		a[i % m].append(x[i])
		i += 1
	for i in a:
		i.sort()
	arr = [ball(a[i][0], i, 0) for i in range(len(a))]
	heapq.heapify(arr)
	mini = arr[0].value
	maxi = [max(arr).value]
	result = maxi[0] - mini
	no_update_min = True
	while no_update_min:
		mini = arr[0].value
		mini_index = arr[0].index
		if maxi[0] - mini < result:
			result = maxi[0] - mini
		no_update_min = update_min(arr, a, mini, maxi, mini_index)
	print(result)


def next(mapping, bucket_count, bucket_count_set, colors, start):
	end = start
	while end < len(mapping):
		(ball, bucket) = mapping[end]
		bucket_count_set.add(bucket)
		bucket_count[bucket] += 1
		if len(bucket_count_set) == colors:
			return (end, bucket_count, bucket_count_set)
		end += 1

def next_2(mapping, bucket_count, bucket_count_set, colors, end):
	if len(bucket_count_set) == colors:
		return (end, bucket_count, bucket_count_set)
	end += 1
	while end < len(mapping):
		(_, bucket) = mapping[end]
		bucket_count_set.add(bucket)
		bucket_count[bucket] += 1
		if len(bucket_count_set) == colors:
			return (end, bucket_count, bucket_count_set)
		end += 1

def ans(mapping, colors):
	bucket_count = [0] * colors
	bucket_count_set = set()
	start = 0
	(end, bucket_count, bucket_count_set) = next(mapping, bucket_count, bucket_count_set, colors, start)
	(start_ball, start_bucket) = mapping[start]
	(end_ball, end_bucket) = mapping[end]
	minimax = end_ball - start_ball
	bucket_count[start_bucket] -= 1
	start += 1
	if bucket_count[start_bucket] == 0:
		bucket_count_set.remove(start_bucket)
	while start < len(mapping):
		ne = next_2(mapping, bucket_count, bucket_count_set, colors, end)
		if ne:
			(end, bucket_count, bucket_count_set) = ne
			(start_ball, start_bucket) = mapping[start]
			(end_ball, _) = mapping[end]
			minimax = min(minimax, end_ball - start_ball)
			bucket_count[start_bucket] -= 1
			start += 1
			if bucket_count[start_bucket] == 0:
				bucket_count_set.remove(start_bucket)
		else:
			return minimax
test = int(input())
while test > 0:
	test -= 1
	(buckets, colors) = map(int, input().split())
	balls = list(map(int, input().split()))
	mapping = []
	for i in range(len(balls)):
		ball = balls[i]
		bucket = i % colors
		mapping.append((ball, bucket))
	mapping.sort()
	print(ans(mapping, colors))


try:
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		vis = [0] * m
		l = list(map(int, input().split()))
		l = list(([l[i], i % m] for i in range(n)))
		l.sort()
		res = l[n - 1][0] - l[0][0]
		s = 0
		for i in l:
			vis[i[1]] += 1
			if vis.count(0) < 1:
				while vis[l[s][1]] > 1:
					vis[l[s][1]] -= 1
					s += 1
				if res > i[0] - l[s][0]:
					res = i[0] - l[s][0]
		print(res)
except EOFError:
	print('0')


INF = 10 ** 9 + 5
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	arr = list(map(int, input().split()))
	pl = {}
	for i in range(N):
		act = arr[i]
		if act not in pl:
			pl[act] = set([i % M])
		else:
			pl[act].add(i % M)
	arr2 = list(pl.keys())
	arr2.sort()
	(i1, i2) = (0, 0)
	acts = [0] * M
	miss = M
	bst = INF
	len2 = len(arr2)
	while i2 < len2:
		while i2 < len2 and miss > 0:
			for idx in pl[arr2[i2]]:
				if acts[idx] == 0:
					miss -= 1
				acts[idx] += 1
			if miss > 0:
				i2 += 1
		if i2 < len2:
			while miss == 0:
				bst = min(bst, arr2[i2] - arr2[i1])
				for idx in pl[arr2[i1]]:
					acts[idx] -= 1
					if acts[idx] == 0:
						miss += 1
				i1 += 1
			i2 += 1
	print(bst)


def find(N, M, arr):
	pos = []
	for i in range(len(arr)):
		pos.append([i % M, i])
	pos.sort(key=lambda x: arr[x[1]])
	arr.sort()
	cnt = [0] * M
	mask = 2 ** M - 1
	i = 0
	j = 0
	while pos[i][0] == pos[j][0]:
		cnt[pos[j][0]] += 1
		j += 1
	cnt[pos[j][0]] += 1
	chk = 1 << pos[i][0]
	chk = chk | 1 << pos[j][0]
	res = float('inf')
	while j < N:
		while chk != mask:
			j += 1
			if j == N:
				break
			chk = chk | 1 << pos[j][0]
			cnt[pos[j][0]] += 1
		if j == N:
			continue
		flag = False
		while True:
			if cnt[pos[i][0]] == 1 and flag:
				break
			if cnt[pos[i][0]] == 1:
				res = min(res, arr[j] - arr[i])
			cnt[pos[i][0]] -= 1
			if cnt[pos[i][0]] < 1:
				chk = chk ^ 1 << pos[i][0]
				flag = True
			i += 1
	return res

def main():
	for i in range(int(input())):
		(N, M) = list(map(int, input().split()))
		arr = list(map(int, input().split()))
		print(find(N, M, arr))
main()


import math
import bisect
t = int(input().strip())
for _ in range(t):
	(n, m) = list(map(int, input().strip().split()))
	a = list(map(int, input().strip().split()))
	if m == n:
		print(max(a) - min(a))
	elif n - m == 1:
		print(min(max(a[:-1]) - min(a[:-1]), max(a[1:]) - min(a[1:])))
	else:
		split = sorted([sorted(a[i::m]) for i in range(m)], key=lambda x: x[-1] - x[0])
		minimum = math.inf
		for num in split[0]:
			val = [num]
			skipped = []
			index = bisect.bisect_left(split[1], val[0])
			if index == 0:
				bisect.insort(val, split[1][0])
			elif index == len(split[1]):
				bisect.insort(val, split[1][-1])
			elif val[0] - split[1][index - 1] < split[1][index] - val[0]:
				bisect.insort(val, split[1][index - 1])
			else:
				bisect.insort(val, split[1][index])
			for i in range(2, len(split)):
				index_1 = bisect.bisect_left(split[i], val[0])
				if index_1 == len(split[i]):
					if split[i][-1] < val[0]:
						bisect.insort(val, split[i][-1])
				elif index_1 == 0:
					if split[i][0] > val[-1]:
						bisect.insort(val, split[i][0])
				elif split[i][index_1] > val[-1]:
					if val[0] - split[i][index_1 - 1] < split[i][index_1] - val[-1]:
						bisect.insort(val, split[i][index_1 - 1])
					else:
						skipped.append(split[i])
			for item in skipped:
				index_1 = bisect.bisect_left(item, val[0])
				if index_1 == 0:
					if item[index_1] > val[-1]:
						bisect.insort(val, item[0])
				elif index_1 == len(item):
					if item[-1] < val[0]:
						bisect.insort(val, item[-1])
				elif item[index_1] > val[-1]:
					if val[0] - item[index_1 - 1] < item[index_1] - val[-1]:
						bisect.insort(val, item[index_1 - 1])
					else:
						bisect.insort(val, item[index_1])
			if minimum > val[-1] - val[0]:
				minimum = val[-1] - val[0]
			if minimum == 0:
				break
		print(minimum)


from collections import OrderedDict
t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	n1 = n
	a = {}
	b = OrderedDict()
	m1 = 1
	ta = map(int, input().split())
	for ii in ta:
		try:
			a[ii].append(m1)
		except:
			a[ii] = []
			a[ii].append(m1)
		m1 += 1
		if m1 > m:
			m1 = 1
	sor = list(a.keys())
	sor.sort()
	mi = sor[-1]
	inc = 0
	for i in sor:
		for j in a[i]:
			try:
				del b[j]
				b[j] = i
			except:
				b[j] = i
				inc += 1
			if inc >= m:
				for value in b:
					break
				mi = min(mi, b[j] - b[value])
	print(mi)
	t -= 1


import heapq
t = int(input())
for o in range(t):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ar = []
	flags = []
	for i in range(m):
		flags.append([])
	for i in range(m):
		ar.append([])
	for i in range(n):
		ar[i % m].append(a[i])
		flags[i % m].append(False)
	for i in range(m):
		ar[i].sort(reverse=True)
	minheap = []
	for i in range(m):
		minheap.append([ar[i][0], [i, 0]])
	maxheap = []
	for i in range(m):
		maxheap.append([-ar[i][0], [i, 0]])
	heapq.heapify(minheap)
	heapq.heapify(maxheap)
	ans = 1000000000001
	try:
		while True:
			maax = heapq.heappop(maxheap)
			miin = heapq.heappop(minheap)
			while flags[miin[1][0]][miin[1][1]] == True:
				miin = heapq.heappop(minheap)
			if -maax[0] - miin[0] < ans:
				ans = -maax[0] - miin[0]
			heapq.heappush(minheap, miin)
			heapq.heappush(maxheap, [-ar[maax[1][0]][maax[1][1] + 1], [maax[1][0], maax[1][1] + 1]])
			heapq.heappush(minheap, [ar[maax[1][0]][maax[1][1] + 1], [maax[1][0], maax[1][1] + 1]])
			flags[maax[1][0]][maax[1][1]] = True
	except Exception as e:
		pass
	print(ans)


import heapq
import sys
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	minimum = sys.maxsize
	j = 0
	temp = [[] for x in range(m)]
	while j < m:
		i = j
		while i < n:
			temp[j].append(l[i])
			i += m
		j += 1
	for i in temp:
		i.sort()
	heap = []
	mini = [sys.maxsize, -1]
	maxi = [-sys.maxsize - 1, -1]
	for i in range(m):
		temp1 = []
		temp1.append(temp[i][0])
		temp1.append(i)
		if temp[i][0] > maxi[0]:
			maxi[0] = temp[i][0]
			maxi[1] = i
		if temp[i][0] < mini[0]:
			mini[0] = temp[i][0]
			mini[1] = i
		heap.append(temp1)
	l = [1] * m
	heapq.heapify(heap)
	rangeRes = sys.maxsize
	while True:
		smallest = heapq.heappop(heap)
		mini[0] = smallest[0]
		if maxi[0] - mini[0] < rangeRes:
			rangeRes = maxi[0] - mini[0]
		if l[smallest[1]] >= len(temp[smallest[1]]):
			break
		temp1 = []
		temp1.append(temp[smallest[1]][l[smallest[1]]])
		temp1.append(smallest[1])
		heapq.heappush(heap, temp1)
		l[smallest[1]] += 1
		if temp1[0] > maxi[0]:
			maxi[0] = temp1[0]
			maxi[1] = smallest[1]
	print(rangeRes)


class Sequence:

	def __init__(self, m):
		self.m = m
		self.stack = []
		self.indexes = []
		self.present = {}
		for i in range(self.m):
			self.present[i] = False

	def isComplete(self):
		if len(self.stack) == self.m:
			return True
		return False

	def isEmpty(self):
		if len(self.stack) == 0:
			return True
		return False

	def push(self, obj):
		self.stack.append(obj)
		self.indexes.append(obj.color)

	def pop(self, index):
		self.stack.pop(index)
		self.indexes.pop(index)

class Box:

	def __init__(self, value, color):
		self.value = value
		self.color = color
tests = int(input())
while tests:
	tests -= 1
	(n, m) = map(int, input().split())
	if m > n:
		m = n
	l = list(map(int, input().split()))
	Boxes = []
	color = 0
	for i in range(n):
		if color == m:
			color = 0
		Boxes.append(Box(l[i], color))
		color += 1
	Boxes.sort(key=lambda x: x.value)
	prev = Boxes[0]
	_min = 10 ** 10
	sequence = Sequence(m)
	for i in range(n):
		if sequence.isEmpty():
			sequence.push(Boxes[i])
			sequence.present[Boxes[i].color] = True
			continue
		if sequence.present[Boxes[i].color]:
			if not sequence.isComplete():
				index = sequence.indexes.index(Boxes[i].color)
				sequence.pop(index)
				sequence.push(Boxes[i])
		else:
			sequence.push(Boxes[i])
			sequence.present[Boxes[i].color] = True
		if sequence.isComplete():
			minBox = sequence.stack[0]
			maxBox = sequence.stack[m - 1]
			sequence.pop(0)
			sequence.present[minBox.color] = False
			_diff = maxBox.value - minBox.value
			if _min > _diff:
				_min = _diff
	print(_min)


for case in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	all_boxes = [int(x) for x in input().split()]
	color_wise_boxes = []
	for j in range(0, n, m):
		for i in range(m):
			try:
				color_wise_boxes.append([all_boxes[i + j], i])
			except IndexError:
				break
	color_wise_boxes.sort()
	initials = {}
	diff = 10000000000.0
	_min = 10000000000.0
	_max = 0
	flag = False
	for box in color_wise_boxes:
		min_flag = False
		try:
			if initials[box[1]] == _min:
				min_flag = True
		except KeyError:
			pass
		initials[box[1]] = box[0]
		if not flag:
			if len(initials) >= m:
				flag = True
		if (initials[box[1]] < _min or initials[box[1]] > _max) and flag:
			if min_flag or _min == 10000000000.0:
				_min = min(initials.values())
			_max = initials[box[1]]
			diff = min(diff, abs(_max - _min))
	print(diff)


import heapq
t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	mat = []
	for i in range(m):
		l = []
		j = 0
		while i + m * j < n:
			l.append(lst[i + m * j])
			j += 1
		l.sort()
		mat.append(l)
	harr = []
	for i in range(m):
		harr.append([mat[i][0], i])
	heapq.heapify(harr)
	index = [0 for i in range(m)]
	lar = max(harr)
	sma = harr[0]
	less = lar[0] - sma[0]
	flag = 1
	if len(mat[sma[1]]) - 1 > index[sma[1]]:
		index[sma[1]] += 1
		sma = heapq.heapreplace(harr, [mat[sma[1]][index[sma[1]]], sma[1]])
	else:
		flag = 0
	count = 0
	x = m
	if n / m > m:
		x = n / m
	while flag:
		lar = max(harr)
		sma = harr[0]
		least = lar[0] - sma[0]
		if least < less:
			less = least
			count = 0
		else:
			count += 1
		if count >= x:
			break
		if len(mat[sma[1]]) - 1 > index[sma[1]]:
			index[sma[1]] += 1
			sma = heapq.heapreplace(harr, [mat[sma[1]][index[sma[1]]], sma[1]])
		else:
			break
	print(less)
	t -= 1


from bisect import insort_left as ins

def rev(a, x):
	lo = 0
	hi = len(a)
	x.pop()
	if not bool(x):
		return True
	while lo < hi:
		mid = (lo + hi) // 2
		if x[-1] > a[mid][-1]:
			hi = mid
		else:
			lo = mid + 1
	a.insert(lo, x)
	return False

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		a = list(map(int, input().split()))
		r = list(range(n))
		mi = 10 ** 9 + 1
		f = [[] for i in range(m)]
		for (i, ia) in enumerate(a):
			ins(a=f[i % m], x=ia)
			if n - i <= m:
				f[i % m].reverse()
		f.sort(reverse=True, key=lambda x: x[-1])
		min = 10 ** 9 + 1
		while True:
			dif = f[0][-1] - f[-1][-1]
			if dif < min:
				min = dif
			x = f.pop()
			if rev(f, x):
				break
		print(min)
main()


import heapq

def smallestRange(A):
	pq = [(row[0], i, 0) for (i, row) in enumerate(A)]
	heapq.heapify(pq)
	ans = (-1000000000.0, 1000000000.0)
	right = max((row[0] for row in A))
	while pq:
		(left, i, j) = heapq.heappop(pq)
		if right - left < ans[1] - ans[0]:
			ans = (left, right)
		if j + 1 == len(A[i]):
			return ans
		v = A[i][j + 1]
		right = max(right, v)
		heapq.heappush(pq, (v, i, j + 1))
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	li = list(map(int, input().split()))
	arr = [[] for j in range(m)]
	for i in range(n):
		arr[i % m].append(li[i])
	for i in arr:
		i.sort()
	x = smallestRange(arr)
	print(abs(x[1] - x[0]))


for t in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if a[i] in d.keys():
			if (i + 1) % m != 0:
				d[a[i]].append((i + 1) % m)
			else:
				d[a[i]].append(m)
		elif (i + 1) % m != 0:
			d[a[i]] = [(i + 1) % m]
		else:
			d[a[i]] = [m]
	a.sort()
	indices = []
	for i in range(n):
		indices.append(d[a[i]][0])
		d[a[i]] = d[a[i]][1:]
	d = [[] for i in range(m)]
	for i in range(n):
		d[indices[i] - 1].append(i)
	tracker = [0 for i in range(m)]
	indices_covered = []
	corr_value = []
	length = 0
	min_diff = 0
	diff = 0
	check = 'false'
	index = 0
	starter = 0
	lowest = 0
	lind = 0
	lcorr = 0
	for i in range(n):
		check = 'false'
		if tracker[indices[i] - 1] == 0:
			tracker[indices[i] - 1] = 1
			indices_covered.append(indices[i])
			lind += 1
			corr_value.append(a[i])
			lcorr += 1
			length += 1
			if length == m:
				for j in range(lowest, lcorr):
					if corr_value[j] != '-':
						min_diff = corr_value[-1] - corr_value[j]
						lowest = j
						break
		else:
			start = indices_covered[lowest]
			index = -(d[indices[i] - 1][1] - d[indices[i] - 1][0])
			corr_value[index] = '-'
			indices_covered[index] = '-'
			for s in range(lowest, lcorr):
				if corr_value[s] != '-':
					lowest = s
					break
			corr_value.append(a[i])
			lcorr += 1
			indices_covered.append(indices[i])
			lind += 1
			del d[indices[i] - 1][0]
			if length != m:
				continue
			if start == indices[i]:
				check = 'true'
			if check == 'true':
				diff = a[i] - corr_value[lowest]
				min_diff = min(min_diff, diff)
	print(min_diff)


class Node:

	def __init__(self, value):
		self.value = value
		self.max_heap_loc = None
		self.min_heap_loc = None
		self.arr_pos = None
		self.index = None
		self.arr_max = None

class MinHeap:

	def __init__(self, arr):
		self.heap = arr
		self.size = len(arr)

	def heapify_down(self, pos):
		left_child = pos * 2 + 1
		right_child = pos * 2 + 2
		if right_child >= len(self.heap):
			if left_child >= len(self.heap):
				return
			min_child = left_child
		else:
			min_child = left_child if self.heap[left_child].value < self.heap[right_child].value else right_child
		if self.heap[pos].value > self.heap[min_child].value:
			self.heap[min_child].min_heap_loc = pos
			self.heap[pos].min_heap_loc = min_child
			(self.heap[pos], self.heap[min_child]) = (self.heap[min_child], self.heap[pos])
			self.heapify_down(min_child)

	def heapify_up(self, pos):
		if pos == 0:
			return
		parent = pos // 2
		if self.heap[parent].value > self.heap[pos].value:
			self.heap[parent].min_heap_loc = pos
			self.heap[pos].min_heap_loc = parent
			(self.heap[parent], self.heap[pos]) = (self.heap[pos], self.heap[parent])
			self.heapify_up(parent)

	def construct_heap(self):
		for i in range((len(self.heap) - 1) // 2, -1, -1):
			self.heapify_down(i)
		self.assign_positions()

	def insert(self, node):
		self.heap.append(node)
		self.heapify_up(self.size)
		self.size += 1

	def peek(self):
		return self.heap[0]

	def show(self):
		a = [(i.value, i.max_heap_loc) for i in self.heap]
		print(a)

	def assign_positions(self):
		for i in range(self.size):
			self.heap[i].min_heap_loc = i

	def change(self, pos, node_new):
		self.heap[pos] = node_new
		if pos == 0:
			self.heapify_down(pos)
		elif self.heap[pos // 2].value < node_new.value:
			self.heapify_down(pos)
		else:
			self.heapify_up(pos)

class MaxHeap:

	def __init__(self, arr):
		self.heap = arr
		self.size = len(arr)

	def heapify_down(self, pos):
		left_child = pos * 2 + 1
		right_child = pos * 2 + 2
		if right_child >= len(self.heap):
			if left_child >= len(self.heap):
				return
			max_child = left_child
		else:
			max_child = left_child if self.heap[left_child].value > self.heap[right_child].value else right_child
		if self.heap[pos].value < self.heap[max_child].value:
			self.heap[max_child].max_heap_loc = pos
			self.heap[pos].max_heap_loc = max_child
			(self.heap[pos], self.heap[max_child]) = (self.heap[max_child], self.heap[pos])
			self.heapify_down(max_child)

	def heapify_up(self, pos):
		if pos == 0:
			return
		parent = pos // 2
		if self.heap[parent].value < self.heap[pos].value:
			self.heap[parent].max_heap_loc = pos
			self.heap[pos].max_heap_loc = parent
			(self.heap[parent], self.heap[pos]) = (self.heap[pos], self.heap[parent])
			self.heapify_up(parent)

	def construct_heap(self):
		for i in range((len(self.heap) - 1) // 2, -1, -1):
			self.heapify_down(i)
		self.assign_positions()

	def insert(self, node):
		self.heap.append(node)
		self.heapify_up(self.size)
		self.size += 1

	def change(self, pos, node_new):
		self.heap[pos] = node_new
		if pos == 0:
			self.heapify_down(pos)
		elif self.heap[pos // 2].value > node_new.value:
			self.heapify_down(pos)
		else:
			self.heapify_up(pos)

	def show(self):
		a = [(i.value, i.min_heap_loc) for i in self.heap]
		print(a)

	def assign_positions(self):
		for i in range(self.size):
			self.heap[i].max_heap_loc = i

	def peek(self):
		return self.heap[0]

def main():
	for i in range(int(input())):
		difs = 10 ** 9
		(n, m) = map(int, input().split())
		arr = list(map(int, input().split()))
		arrs = [[] for u in range(m)]
		j = 0
		for i in arr:
			n = Node(i)
			n.arr_pos = j % m
			arrs[j % m].append(n)
			j += 1
		for ar in arrs:
			ar.sort(key=lambda x: x.value)
			x = len(ar)
			for i in range(x):
				ar[i].index = i
				ar[i].arr_max = x
		minh = MinHeap([k[0] for k in arrs])
		maxh = MaxHeap([k[0] for k in arrs])
		minh.construct_heap()
		maxh.construct_heap()
		while True:
			top_min = minh.peek()
			top_max = maxh.peek()
			dif = top_max.value - top_min.value
			if dif < difs:
				difs = dif
			if top_min.index >= top_min.arr_max - 1:
				break
			next_min = arrs[top_min.arr_pos][top_min.index + 1]
			(next_min.min_heap_loc, next_min.max_heap_loc) = (top_min.min_heap_loc, top_min.max_heap_loc)
			minh.change(0, next_min)
			maxh.change(top_min.max_heap_loc, next_min)
		print(difs)
main()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	mat = []
	for j in range(m):
		temp = [arr[i] for i in range(j, n, m)]
		temp.sort()
		mat.append(temp)
	mini = 10 ** 10
	flag = 0
	temp = [mat[i][0] for i in range(m)]
	count = 0
	while flag != 1 and mini != 0 and (count < 2000):
		count += 1
		if max(temp) - min(temp) < mini:
			mini = max(temp) - min(temp)
		my_index = arr.index(min(temp)) % m
		arr[arr.index(min(temp))] = -1
		mat[my_index].pop(0)
		if len(mat[my_index]) == 0:
			flag = 1
			break
		temp.remove(min(temp))
		if len(mat[my_index]) != 0:
			temp.append(mat[my_index][0])
	print(mini)


from collections import defaultdict
import sys

class Node:

	def __init__(self, ele, list_i, next_i):
		self.ele = ele
		self.list_i = list_i
		self.next_i = next_i

class MinHeap:

	def __init__(self, arr, size):
		self.arr = arr
		self.size = size
		i = size // 2
		while i >= 0:
			self.MinHeapify(i)
			i -= 1

	def left(self, i):
		return 2 * i + 1

	def right(self, i):
		return 2 * i + 2

	def MinHeapify(self, i):
		l = self.left(i)
		r = self.right(i)
		small = i
		if l < self.size and self.arr[l].ele < self.arr[i].ele:
			small = l
		if r < self.size and self.arr[r].ele < self.arr[small].ele:
			small = r
		if small != i:
			self.swap(small, i)
			self.MinHeapify(small)

	def swap(self, i, j):
		temp = self.arr[i]
		self.arr[i] = self.arr[j]
		self.arr[j] = temp

	def getMin(self):
		return self.arr[0]

	def replaceMin(self, x):
		self.arr[0] = x
		self.MinHeapify(0)

def findSmallestRange(boxes, m):
	minrange = sys.maxsize
	minV = sys.maxsize
	maxV = -sys.maxsize - 1
	(start, end) = (-1, -1)
	arr = [0] * m
	for i in range(0, m):
		node = Node(boxes[i][0], i, 1)
		arr[i] = node
		maxV = max(maxV, node.ele)
	mh = MinHeap(arr, m)
	while True:
		root = mh.getMin()
		minV = root.ele
		if minrange > maxV - minV:
			minrange = maxV - minV
			start = minV
			end = maxV
		if root.next_i < len(boxes[root.list_i]):
			root.ele = boxes[root.list_i][root.next_i]
			root.next_i += 1
			if root.ele > maxV:
				maxV = root.ele
		else:
			break
		mh.replaceMin(root)
	print(minrange)
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	arr = list(map(int, input().split()))
	boxes = defaultdict(list)
	count = 0
	for i in range(N):
		box_index = count % M
		boxes[box_index].append(arr[i])
		count += 1
	for i in range(M):
		boxes[i].sort()
	findSmallestRange(boxes, M)


import heapq

def smallest_interval(nums):
	heap = [(row[0], i, 0) for (i, row) in enumerate(nums)]
	heapq.heapify(heap)
	local_maximum = max((row[0] for row in nums))
	ans = [-10 ** 10, 10 ** 10]
	while heap:
		(local_minimum, num_list, local_min_index) = heapq.heappop(heap)
		if local_maximum - local_minimum < ans[1] - ans[0]:
			ans = [local_minimum, local_maximum]
		if local_min_index + 1 == len(nums[num_list]):
			return ans
		next_val = nums[num_list][local_min_index + 1]
		local_maximum = max(next_val, local_maximum)
		heapq.heappush(heap, (next_val, num_list, local_min_index + 1))
t = int(input())
for _ in range(t):
	[n, m] = list(map(int, input().split()))
	l = list(map(int, input().split()))
	a = []
	for i in range(m):
		k = []
		a.append(k)
	i = 0
	while i < n:
		count = 0
		while count < m:
			if i < n:
				a[count].append(l[i])
				count += 1
				i += 1
			if i >= n and count < m:
				a[count].append(10 ** 10)
				count += 1
				i += 1
	for num in a:
		num.sort()
	if n % m == 0:
		N = n // m
	else:
		N = n // m + 1
	ans = smallest_interval(a)
	print(ans[1] - ans[0])


import bisect
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().strip().split()))
	l = list(map(int, input().strip().split()))
	s = [sorted(l[i::m]) for i in range(m)]
	s2 = sorted(s, key=lambda x: x[-1] - x[0])
	res = 100000000000
	for val in s2[0]:
		small = val
		ind = bisect.bisect_left(s2[1], small)
		if ind == 0:
			large = s2[1][ind]
		elif ind == len(s2[1]):
			large = small
			small = s2[1][-1]
		elif small - s2[1][ind - 1] < s2[1][ind] - small:
			large = small
			small = s2[1][ind - 1]
		else:
			large = s2[1][ind]
		if len(s2) > 2:
			emptyList = []
			for i in range(2, len(s2)):
				indd = bisect.bisect_left(s2[i], small)
				if indd == len(s2[i]):
					if s2[i][-1] < small:
						small = s2[i][-1]
				elif indd == 0:
					if s2[i][indd] > large:
						large = s2[i][0]
				elif s2[i][indd] > large:
					if small - s2[i][indd - 1] < s2[i][indd] - large:
						small = s2[i][indd - 1]
					elif small - s2[i][indd - 1] < s2[i][indd] - large:
						large = s2[i][indd]
					else:
						emptyList.append(s2[i])
			for sel in emptyList:
				indd = bisect.bisect_left(sel, small)
				if indd == len(s2[i]):
					if sel[-1] < small:
						small = sel[-1]
				elif indd == 0:
					if sel[indd] > large:
						large = sel[0]
				elif sel[indd] > large:
					if small - sel[indd - 1] < sel[indd] - large:
						small = sel[indd - 1]
					elif small - sel[indd - 1] < sel[indd] - large:
						large = sel[indd]
					else:
						large = sel[indd]
		if large - small < res:
			res = large - small
		if res == 0:
			break
	print(res)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ll = list(map(int, input().split()))
	a = []
	for i in range(n):
		a.append([])
		a[i].append(ll[i])
		a[i].append(i % m)
	l = sorted(a, key=lambda lll: lll[0])
	a = [0] * m
	j = 0
	ans = 0
	for i in range(n):
		if a[l[i][1]] == 0:
			ans += 1
		a[l[i][1]] += 1
		if ans == m:
			j = i
			ans = l[i][0] - l[0][0]
			break
	for i in range(1, n - m + 1):
		if ans == 0:
			break
		index = l[i - 1][1]
		a[index] -= 1
		if a[index] != 0:
			ans = min(ans, l[j][0] - l[i][0])
		else:
			for k in range(j + 1, n):
				a[l[k][1]] += 1
				if l[k][1] == index:
					j = k
					ans = min(ans, l[j][0] - l[i][0])
					break
			else:
				break
	print(ans)


import heapq
import sys
sys.setrecursionlimit(100000)

class Boxes:

	def __init__(self, N, M):
		self.M = M
		self.N = N
		self.A = []
		heapq.heapify(self.A)
		self.ChoosenDict = dict()
		self.Choosen = []
		heapq.heapify(self.Choosen)
		self.minVal = None
		self.maxVal = None
		self.minDiff = -1

	def input(self, inputArr):
		index = 0
		for a in inputArr:
			w = int(a)
			ao = [w, index % self.M]
			heapq.heappush(self.A, (w, ao))
			index += 1

	def check(self):
		for _ in range(N):
			box = heapq.heappop(self.A)[1]
			self.addInChoise(box)
		print(self.minDiff)

	def addInChoise(self, box):
		self.maxVal = box
		pop = self.minVal is None or (box[1] in self.ChoosenDict and self.ChoosenDict[box[1]] == self.minVal)
		self.ChoosenDict[box[1]] = box
		heapq.heappush(self.Choosen, (box[0], box))
		if pop:
			self.minVal = heapq.heappop(self.Choosen)[1]
			while self.ChoosenDict[self.minVal[1]][0] != self.minVal[0]:
				self.minVal = heapq.heappop(self.Choosen)[1]
		if len(self.ChoosenDict.keys()) == M:
			diff = self.maxVal[0] - self.minVal[0]
			if self.minDiff == -1 or diff < self.minDiff:
				self.minDiff = diff
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	boxes = Boxes(N, M)
	boxes.input(input().split())
	boxes.check()


from queue import PriorityQueue
II = lambda : [int(x) for x in input().split()]
T = int(input())
for _ in range(T):
	(N, M) = II()
	A = II()
	matrix = [list() for _ in range(M)]
	for i in range(N):
		matrix[i % M].append(A[i])
	for i in range(M):
		matrix[i].sort()
	pointers = [0] * M
	V = [matrix[j][0] for j in range(M)]
	(max_c, min_c) = (max(V), min(V))
	diff = max_c - min_c
	Q = PriorityQueue()
	for (j, p) in enumerate(pointers):
		Q.put((matrix[j][p], (j, p)))
	while not Q.empty():
		(min_c, item) = Q.get()
		if max_c - min_c < diff:
			diff = max_c - min_c
		(j, p) = item
		p += 1
		if p == len(matrix[j]):
			break
		Q.put((matrix[j][p], (j, p)))
		if matrix[j][p] > max_c:
			max_c = matrix[j][p]
	print(diff)


def inp():
	t = int(input())
	while t > 0:
		(n, m) = map(int, input().split())
		a = list(map(int, input().split()))
		count = 0
		pairs = []
		for num in a:
			pairs.append((num, count % m))
			count += 1
		pairs.sort()
		newList = a[:m]
		maxi = max(newList)
		mini = min(newList)
		diff = maxi - mini
		for i in range(0, n):
			miniflag = False
			maxiFlag = False
			if newList[pairs[i][1]] == mini:
				miniflag = True
			if newList[pairs[i][1]] == maxi:
				maxiFlag = True
			newList[pairs[i][1]] = pairs[i][0]
			if miniflag == True or maxiFlag == True:
				mini = min(newList)
				maxi = max(newList)
			else:
				maxi = max(maxi, pairs[i][0])
			diff = min(diff, maxi - mini)
		print(diff)
		t = t - 1
inp()


import bisect

def insert(l, n):
	bisect.insort(l, n)
	return l
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ins = n // k
	a = [[] for i in range(k)]
	for i in range(k):
		for j in range(i, n, k):
			a[i].append(arr[j])
	for i in a:
		i.sort()
	heap = [i[0] for i in a]
	temp = list(heap)
	temp.sort()
	minhp = temp[0]
	maxhp = temp[-1]
	diff = maxhp - minhp
	pos = [0] * k
	ln = [len(i) for i in a]
	status = True
	while status:
		inx = heap.index(minhp)
		pos[inx] += 1
		if pos[inx] > ln[inx] - 1:
			status = False
			break
		element = heap[inx]
		heap[inx] = a[inx][pos[inx]]
		temp.remove(element)
		insert(temp, a[inx][pos[inx]])
		minhp = temp[0]
		maxhp = temp[-1]
		diff1 = maxhp - minhp
		if diff1 < diff:
			diff = diff1
	print(diff)


class MinHeapNode:

	def __init__(self):
		self.element = 0
		self.i = 0
		self.j = 0

class MinHeap:

	def __init__(self, a, size):
		self.heap_size = size
		self.harr = a
		i = (self.heap_size - 1) // 2
		while i >= 0:
			self.MinHeapify(i)
			i -= 1

	def left(self, i):
		return 2 * i + 1

	def right(self, i):
		return 2 * i + 2

	def getMin(self):
		return self.harr[0]

	def replaceMin(self, x):
		self.harr[0] = x
		self.MinHeapify(0)

	def MinHeapify(self, i):
		l = self.left(i)
		r = self.right(i)
		smallest = i
		if l < self.heap_size and self.harr[l].element < self.harr[i].element:
			smallest = l
		if r < self.heap_size and self.harr[r].element < self.harr[smallest].element:
			smallest = r
		if smallest != i:
			temp = self.harr[i]
			self.harr[i] = self.harr[smallest]
			self.harr[smallest] = temp
			self.MinHeapify(smallest)

def findSmallestRange(arr, k, N):
	rangee = float('inf')
	minn = float('inf')
	maxx = -float('inf')
	harr = [0 for i in range(k)]
	for i in range(k):
		harr[i] = MinHeapNode()
		harr[i].element = arr[i][0]
		harr[i].i = i
		harr[i].j = 1
		if harr[i].element > maxx:
			maxx = harr[i].element
	hp = MinHeap(harr, k)
	while 1:
		root = hp.getMin()
		minn = hp.getMin().element
		if rangee > maxx - minn + 1:
			rangee = maxx - minn + 1
			start = minn
			end = maxx
		if root.j < N[root.i]:
			root.element = arr[root.i][root.j]
			root.j += 1
			if root.element > maxx:
				maxx = root.element
		else:
			break
		hp.replaceMin(root)
	print(end - start)
t = int(input())
for i in range(t):
	(n, m) = [int(i) for i in input().split()]
	temp = [int(i) for i in input().split()]
	arr = [[] for i in range(m)]
	N = [0 for i in range(m)]
	for i in range(n):
		arr[i % m].append(temp[i])
		N[i % m] += 1
	for i in range(m):
		arr[i].sort()
	findSmallestRange(arr, m, N)


def customSort(a):
	return a[0]
T = int(input())
for t in range(T):
	(N, M) = list(map(int, input().strip().split(' ')))
	A_temp = list(map(int, input().strip().split(' ')))
	A = []
	for n in range(N):
		A.append([A_temp[n], n % M])
	A = sorted(A, key=customSort)
	colors = set()
	boxes = dict()
	diffs = []
	min_element_index = 0
	insertedBoxes = []
	indexOfColors = dict()
	valuesOfIndex = dict()
	for i in range(N):
		max_element = A[i][0]
		if A[i][1] in indexOfColors:
			del valuesOfIndex[indexOfColors[A[i][1]]]
		boxes[A[i][1]] = A[i][0]
		indexOfColors[A[i][1]] = i
		insertedBoxes.append(A[i][0])
		valuesOfIndex[i] = A[i][0]
		colors.add(A[i][1])
		if len(colors) == M:
			min_element = list(valuesOfIndex.values())[0]
			diffs.append(max_element - min_element)
	ans = min(diffs)
	print(ans)


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	currArr = [arr[x] for x in range(m)]
	arr = [[arr[x], x % m] for x in range(n)]
	arr = sorted(arr)
	maxVal = max(currArr)
	minVal = min(currArr)
	answer = maxVal - minVal
	for x in range(0, len(arr)):
		(a, b) = arr[x]
		if currArr[b] == maxVal:
			currArr[b] = a
			maxVal = max(currArr)
			minVal = min(currArr)
		if currArr[b] == minVal:
			currArr[b] = a
			minVal = min(currArr)
			maxVal = max(currArr)
		currArr[b] = a
		if maxVal - minVal < answer:
			answer = maxVal - minVal
	print(answer)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = []
	c = 1
	for v in map(int, input().split()):
		l += [(v, c)]
		if c == m:
			c = 1
		else:
			c += 1
	l = sorted(l, key=lambda x: x[0])
	a = [0] * (m + 1)
	s = set()
	w = []
	res = 1000000009
	i = 0
	while 1:
		while len(s) != m and i < n:
			s.add(l[i][1])
			a[l[i][1]] += 1
			w += [l[i]]
			i += 1
		if len(s) == m:
			res = min(res, abs(w[0][0] - w[-1][0]))
		if w[0] == w[-1]:
			break
		a[w[0][1]] -= 1
		if a[w[0][1]] == 0:
			s.remove(w[0][1])
		w.pop(0)
	print(res)


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	a = [i % m for i in range(n)]
	l1 = []
	values = []
	a = [a for (_, a) in sorted(zip(l, a))]
	l.sort()
	max_val = 99999999999
	arr = [-1 for x in range(m)]
	for i in range(n):
		arr[a[i]] = i
		if -1 not in arr:
			m1 = max(arr)
			m2 = min(arr)
			if max_val > l[m1] - l[m2]:
				max_val = l[m1] - l[m2]
			arr[arr.index(m2)] = -1
	print(max_val)


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	ar = list(map(int, input().split()))
	col = 0
	arr = []
	for i in range(n):
		arr.append([ar[i], col % m])
		col += 1
	arr.sort(key=lambda x: x[0])
	dic = {}
	i = j = 0
	ans = float('inf')
	while j < n:
		dic[arr[j][1]] = dic.get(arr[j][1], 0) + 1
		while dic and dic[arr[i][1]] > 1:
			dic[arr[i][1]] -= 1
			i += 1
		if len(dic) == m:
			ans = min(ans, arr[j][0] - arr[i][0])
		j += 1
	print(ans)


import heapq as heap
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	L = list(map(int, input().split()))
	arr = [[] for i in range(M)]
	ind = 0
	for i in L:
		arr[ind].append(i)
		ind = (ind + 1) % M
	for i in range(len(arr)):
		arr[i].sort()
	arr.sort()
	max_elem = arr[-1][0]
	H = [(arr[i][0], i, 0) for i in range(len(arr))]
	heap.heapify(H)
	min_diff = max_elem - H[0][0]
	while True:
		min_diff = min(min_diff, max_elem - H[0][0])
		rem = heap.heappop(H)
		if len(arr[rem[1]]) - 1 == rem[2]:
			break
		heap.heappush(H, (arr[rem[1]][rem[2] + 1], rem[1], rem[2] + 1))
		max_elem = max(max_elem, arr[rem[1]][rem[2] + 1])
	print(min_diff)


from heapq import *
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [(a[i], i % m) for i in range(n)]
	b.sort()
	color_index = {}
	for i in range(m):
		color_index[i] = []
	for i in range(n):
		color_index[b[i][1]].append(b[i])
	pointers = [0 for i in range(m)]
	minheap = []
	maxheap = []
	for i in range(m):
		heappush(minheap, color_index[i][0])
		heappush(maxheap, -color_index[i][0][0])
	diff = 1000000000
	while True:
		minitem = heappop(minheap)
		maxitem = maxheap[0]
		x = minitem[1]
		diff = min(-1 * maxitem - minitem[0], diff)
		pointers[x] += 1
		if pointers[x] == len(color_index[x]):
			break
		else:
			item = color_index[x][pointers[x]]
			heappush(minheap, item)
			heappush(maxheap, -item[0])
	print(diff)