Chef has two arrays A and B of the same size N.

In one operation, Chef can:
Choose two integers i and j (1 ≤ i, j ≤ N) and swap the elements A_{i} and B_{j}.

Chef came up with a task to find the minimum possible value of (A_{max} - A_{min}) after performing the swap operation any (possibly zero) number of times. 

Since Chef is busy, can you help him solve this task?

Note that A_{max} and A_{min} denote the maximum and minimum elements of the array A respectively.

------ 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 one integer N — the number of elements in each array.
- The second line consists of N space-separated integers A_{1}, A_{2},\ldots ,A_{N} denoting the elements of the array A.
- The third line consists of N space-separated integers B_{1}, B_{2}, \ldots ,B_{N} denoting the elements of the array B.

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

For each test case, output on a new line, the minimum possible value of (A_{max} - A_{min}) in the array A after doing swap operation any number of times.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$1 ≤ A_{i}, B_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3
2 1 3
1 4 1
4
2 1 4 3
3 2 6 2
5
2 8 4 9 7
7 3 6 8 4

----- Sample Output 1 ------ 
0
1
2
----- explanation 1 ------ 
Test case $1$: Chef can make the following operations:
- Operation $1$: Choose $i=1$ and $j=1$ and swap $A_{1}$ with $B_{1}$.
- Operation $2$: Choose $i=3$ and $j = 3$ and swap $A_{3}$ with $B_{3}$.

By doing the above operations, array $A$ becomes $[1, 1, 1]$. Here $(A_{max} - A_{min}) = 0$. It can be shown that this is the minimum value possible.

Test case $2$: Chef can make the following operations:
- Operation $1$: Choose $i=2$ and $j=2$ and swap $A_{2}$ with $B_{2}$.
- Operation $2$: Choose $i=3$ and $j=1$ and swap $A_{3}$ with $B_{1}$.
- Operation $3$: Choose $i=4$ and $j=4$ and swap $A_{4}$ with $B_{4}$.

By doing the above operations, array $A$ becomes $[2, 2, 3, 2]$. Here $(A_{max} - A_{min}) = 1$. It can be shown that this is the minimum value possible.

Test case $3$: Chef can make the following operations:
- Operation $1$: Choose $i=1$ and $j=1$ and swap $A_{1}$ with $B_{1}$.
- Operation $2$: Choose $i=3$ and $j=4$ and swap $A_{3}$ with $B_{4}$.

By doing the above operations, array $A$ becomes $[7, 8, 8, 9, 7]$. Here $(A_{max} - A_{min}) = 2$. It can be shown that this is the minimum value possible.

Source: codechef | Difficulty: EASY
Tags: Data structures

Sorting

Amortized analysis


Solutions:
for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	l = l + m
	l.sort()
	i = 0
	k = 9999999999
	while i <= a:
		k = min(k, l[i + a - 1] - l[i])
		i += 1
	print(k)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a = a + b
	a.sort()
	b = []
	for i in range(n + 1):
		b.append(a[n + i - 1] - a[i])
	print(min(b))


for _ in range(int(input())):
	N = int(input())
	L1 = list(map(int, input().split()))
	L2 = list(map(int, input().split()))
	L = sorted(L1 + L2)
	res = 999999999
	for i in range(N + 1):
		res = min(res, L[i + N - 1] - L[i])
	print(res)


import sys
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	merge = list(a + b)
	merge.sort()
	myn = sys.maxsize
	for j in range(n + 1):
		myn = min(myn, merge[n + j - 1] - merge[j])
	print(myn)


t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = A + B
	C.sort()
	D = []
	for i in range(n + 1):
		D.append(C[n + i - 1] - C[i])
	print(min(D))


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = a + b
	c.sort()
	d = []
	for i in range(n + 1):
		d.append(c[n + i - 1] - c[i])
	sys.stdout.write(str(min(d)) + '\n')


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a += b
	a.sort()
	c = max(a)
	for i in range(n + 1):
		c = min(a[n + i - 1] - a[i], c)
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = a + b
	c.sort()
	d = max(c)
	e = []
	for i in range(n + 1):
		e.append(c[n + i - 1] - c[i])
	print(min(e))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = a + b
	c.sort()
	diff = c[n - 1] - c[0]
	for i in range(1, n + 1):
		if c[i + n - 1] - c[i] < diff:
			diff = c[i + n - 1] - c[i]
	print(diff)


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = A + B
	C.sort()
	MIN = C[-1] - C[0]
	for i in range(N + 1):
		MIN = min(MIN, C[i + N - 1] - C[i])
	print(MIN)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = sorted(a + b)
	l = []
	for i in range(n + 1):
		l.append(c[n + i - 1] - c[i])
	print(min(l))


b = int(input())
for i in range(b):
	N = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	k = a + b
	k.sort()
	t = k
	o = t[len(a) - 1] - t[0]
	for h in range(len(k) - len(a) + 1):
		if o > -t[h] + t[h + len(a) - 1]:
			o = -t[h] + t[h + len(a) - 1]
	print(o)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = a + b
	c.sort()
	min = c[2 * n - 1] - c[0]
	for i in range(n + 1):
		k = c[i + n - 1] - c[i]
		if k < min:
			min = k
	print(min)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	l = sorted(a + b)
	min = l[-1] - l[0]
	for i in range(n + 1):
		if l[n + i - 1] - l[i] < min:
			min = l[n + i - 1] - l[i]
	print(min)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = sorted(a + b)
	l = []
	for j in range(n + 1):
		d = c[j + n - 1] - c[j]
		l.append(d)
	print(min(l))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = a + b
	l.sort(reverse=True)
	c = []
	for i in range(n + 1):
		c.append(l[i] - l[i + n - 1])
	print(min(c))


import sys
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	c = a + b
	min1 = sys.maxsize
	c.sort()
	for i in range(n + 1):
		min1 = min(min1, c[n + i - 1] - c[i])
	print(min1)


for _ in range(int(input())):
	n = int(input())
	l1 = [int(i) for i in input().split()]
	l2 = [int(i) for i in input().split()]
	l1 = l1 + l2
	l1.sort()
	i = 0
	j = n - 1
	diff = l1[j] - l1[i]
	while j < 2 * n:
		if l1[j] - l1[i] < diff:
			diff = l1[j] - l1[i]
		j += 1
		i += 1
	print(diff)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = sorted(a + b)
	L = []
	i = 0
	for j in range(n - 1, len(c)):
		L.append(abs(c[i] - c[j]))
		i = i + 1
	print(min(L))


import sys
t = int(input())
for x in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = a + b
	c.sort()
	req = sys.maxsize
	for j in range(n + 1):
		req = min(req, c[n + j - 1] - c[j])
	print(req)


for i in range(int(input())):
	n = int(input())
	l1 = [int(i) for i in input().split()]
	l2 = [int(i) for i in input().split()]
	l = l1 + l2
	l = sorted(l)
	l1 = l[:n]
	l2 = l[n:]
	j = 0
	r = []
	for i in range(n - 1, len(l)):
		r.append(abs(l[j] - l[i]))
		j += 1
	print(min(r))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	c = sorted(a + b)
	minn = max(c)
	j = 0
	for i in range(n - 1, len(c)):
		minn = min(minn, c[i] - c[j])
		j += 1
	print(minn)


for _ in range(int(input())):
	x = int(input())
	l1 = sorted(list(map(int, input().split())))
	l2 = sorted(list(map(int, input().split())))
	l1.extend(l2)
	l1 = sorted(l1)
	y = []
	for i in range(x + 1):
		y.append(l1[i + x - 1] - l1[i])
	print(min(y))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = l + list(map(int, input().split()))
	m.sort()
	p = 90909090909
	for i in range(n + 1):
		p = min(m[i + n - 1] - m[i], p)
	print(p)


for i in range(int(input())):
	N = int(input())
	l1 = list(map(int, input().split()))
	l2 = l1 + list(map(int, input().split()))
	l2.sort()
	minimum = 9999999999999999999999999999999999
	for i in range(N + 1):
		minimum = min(l2[i + (N - 1)] - l2[i], minimum)
	print(minimum)


t = int(input())
for i in range(t):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = arr1 + list(map(int, input().split()))
	arr2.sort()
	minimum = 9999999999999999999999999999999999
	for i in range(n + 1):
		minimum = min(arr2[i + (n - 1)] - arr2[i], minimum)
	print(minimum)


from collections import Counter, defaultdict
from sys import stdin, stdout, setrecursionlimit
from heapq import nlargest, nsmallest
import math
setrecursionlimit(2147400000)

def outnl(x):
	stdout.write(str(x) + '\n')

def outsl(x):
	stdout.write(str(x) + ' ')

def instr():
	return stdin.readline().strip()

def inint():
	return int(stdin.readline())

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

def inlist():
	return list(map(int, stdin.readline().strip().split()))
for _ in range(inint()):
	n = inint()
	a = inlist()
	b = inlist()
	arr = a + b
	arr.sort()
	ans = float('inf')
	for i in range(n + 1):
		mini = arr[i]
		maxi = arr[i + n - 1]
		ans = min(maxi - mini, ans)
	print(ans)


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = sorted(a + b)
	m = c[n - 1] - c[0]
	for j in range(1, n + 1):
		m = min(m, c[j + n - 1] - c[j])
	print(m)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a += b
	a.sort()
	mn = a[n - 1] - a[0]
	for i in range(1, n + 1):
		if mn > a[i + n - 1] - a[i]:
			mn = a[i + n - 1] - a[i]
	print(mn)


import sys
for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	x.extend(y)
	x.sort()
	mn = sys.maxsize
	for i in range(n + 1):
		mn = min(mn, x[n + i - 1] - x[i])
	print(mn)


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	AB = sorted(A + B)
	ans = 1000000000
	for n in range(N + 1):
		ans = min(ans, AB[n + N - 1] - AB[n])
	print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	P = sorted(A + B)
	m = P[N - 1] - P[0]
	for j in range(1, N + 1):
		m = min(m, P[j + N - 1] - P[j])
	print(m)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	A = sorted(inlt() + inlt())
	ans.append(min((A[i + N - 1] - A[i] for i in range(N + 1))))
outplt(ans)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l1 += l2
	l1.sort()
	m = l1[n - 1] - l1[0]
	for i in range(1, n + 1):
		m = min(m, l1[i + n - 1] - l1[i])
	print(m)


import sys
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	y = list(a + b)
	y.sort()
	x = sys.maxsize
	for j in range(n + 1):
		x = min(x, y[n + j - 1] - y[j])
	print(x)


import sys
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	m = sorted(list(a + b))
	l = sys.maxsize
	for i in range(n + 1):
		l = min(l, m[n + i - 1] - m[i])
	print(l)


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = a + b
	s = sorted(s)
	A = s[n - 1] - s[0]
	for i in range(1, n + 1):
		k = s[i + n - 1] - s[i]
		if k < A:
			A = k
	print(A)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	c = sorted(a + b)
	ans = float('inf')
	for j in range(n + 1):
		ans = min(ans, c[n - 1 + j] - c[j])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l = l1 + l2
	l.sort()
	m = l[n - 1] - l[0]
	for i in range(1, n + 1):
		k = l[i + n - 1] - l[i]
		if k < m:
			m = k
	print(m)


n = int(input())
for i in range(n):
	a = int(input())
	l = list(map(int, input().split()))
	m = list(map(int, input().split()))
	k = l + m
	k.sort()
	c = k[a - 1] - k[0]
	for s in range(a + 1):
		if k[a + s - 1] - k[s] < c:
			c = k[a + s - 1] - k[s]
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.extend(b)
	a = sorted(a)
	minm = a[n - 1] - a[0]
	for i in range(n + 1):
		minm = min(minm, a[i + n - 1] - a[i])
	print(minm)


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = a + b
	c.sort()
	m = sys.maxsize
	for i in range(n + 1):
		m = min(m, c[n + i - 1] - c[i])
	print(m)


for _ in range(int(input())):
	N = int(input())
	A = list(map(lambda x: int(x), input().split(' ')))
	B = list(map(lambda x: int(x), input().split(' ')))
	C = list(A + B)
	C.sort()
	min = C[N + 0 - 1] - C[0]
	for i in range(N + 1):
		if C[N + i - 1] - C[i] < min:
			min = C[N + i - 1] - C[i]
	print(min)


t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	arr = sorted(A + B)
	m = max(arr)
	for i in range(n + 1):
		if arr[i + n - 1] - arr[i] < m:
			m = arr[i + n - 1] - arr[i]
	print(m)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	c = a + b
	c.sort()
	mi = max(c)
	for i in range(n + 1):
		if c[i + n - 1] - c[i] < mi:
			mi = c[i + n - 1] - c[i]
	print(mi)


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.extend(b)
	a.sort()
	difi = sys.maxsize
	for i in range(n + 1):
		mini = a[n + i - 1] - a[i]
		difi = min(difi, mini)
	print(difi)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = A + B
	C.sort()
	min = None
	for i in range(N + 1):
		if min is None:
			min = C[N - 1] - C[0]
		elif min > C[i + N - 1] - C[i]:
			min = C[i + N - 1] - C[i]
	print(min)


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = a + b
	c.sort()
	diff = 10000000000
	cn = len(c)
	for i in range(cn):
		if 0 < i + n - 1 < cn:
			cur = abs(c[i] - c[i + n - 1])
			if cur < diff:
				diff = cur
	print(diff)


T = int(input())
for _ in range(T):
	N = int(input())
	arr = []
	arr = list(map(int, input().strip().split()))
	brr = list(map(int, input().strip().split()))
	arr.extend(brr)
	arr.sort()
	mn = 10000000007
	for i in range(N - 1, 2 * N):
		if arr[i] - arr[i - N + 1] < mn:
			mn = arr[i] - arr[i - N + 1]
	print(mn)


import sys
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split(' ')))
	br = list(map(int, input().split(' ')))
	ar.sort()
	br.sort()
	a = []
	i = 0
	j = 0
	while i < n and j < n:
		if ar[i] < br[j]:
			a.append(ar[i])
			i += 1
		else:
			a.append(br[j])
			j += 1
	while i < n:
		a.append(ar[i])
		i += 1
	while j < n:
		a.append(br[j])
		j += 1
	ans = 10 ** 9
	i = 0
	j = n - 1
	while j < len(a):
		ans = min(ans, a[j] - a[i])
		i += 1
		j += 1
	print(ans)


L = []
import sys
T = int(input())
for q in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	merge = list(A + B)
	merge.sort()
	a = sys.maxsize
	for i in range(N + 1):
		s = i
		e = i + N - 1
		a = min(a, merge[e] - merge[s])
	print(a)


for _ in range(int(input())):
	n = int(input())
	la = list(map(int, input().split()))
	lb = list(map(int, input().split()))
	main = la + lb
	main.sort()
	i = 0
	a = 1000000000
	while i <= n:
		s = i
		e = i + n - 1
		a = min(a, main[e] - main[s])
		i += 1
	print(a)


import sys
t = int(input())
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	temp = a + b
	temp.sort()
	ans = sys.maxsize
	for i in range(n + 1):
		ans = min(ans, temp[i + n - 1] - temp[i])
	print(ans)
	t -= 1


import sys
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	m = list(a + b)
	m.sort()
	mi = sys.maxsize
	for j in range(n + 1):
		mi = min(mi, m[n + j - 1] - m[j])
	print(mi)


import sys
T = int(input())
for _ in range(T):
	arraySize = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	sortedList = sorted(A + B)
	minimum = sys.maxsize
	for i in range(arraySize + 1):
		minimum = min(minimum, sortedList[arraySize + i - 1] - sortedList[i])
	print(minimum)