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

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

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
2
1 2
2 1
3
1 5 3
2 3 1
4
4 2 5 1
5 3 4 1

----- Sample Output 1 ------ 
0
1
3

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

By doing the above operations, array $A$ becomes $[2, 2]$. 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=1$ and swap $A_{1}$ with $B_{1}$.
- Operation $2$: Choose $i=2$ and swap $A_{2}$ with $B_{2}$.

By doing the above operations, array $A$ becomes $[2, 3, 3]$. 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=2$ and swap $A_{2}$ with $B_{2}$.
- Operation $2$: Choose $i=3$ and swap $A_{3}$ with $B_{3}$.

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

Difficulty: HARD
Tags: Data structures

Sorting

Amortized analysis

Greedy algorithms
Skill types: Sorting

Amortized analysis

Data structures

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	arr1 = list(map(int, input().split(' ')))
	arr2 = list(map(int, input().split(' ')))
	for i in range(N):
		if arr1[i] < arr2[i]:
			(arr1[i], arr2[i]) = (arr2[i], arr1[i])
	arr = []
	for i in range(N):
		col = []
		col.append(arr1[i])
		col.append(arr2[i])
		arr.append(col)
	arr.sort()
	(arr1Min, arr1Max, arr2Min, arr2Max) = ([0] * N, [0] * N, [0] * N, [0] * N)
	arr1Min[0] = arr[0][0]
	arr1Max[0] = arr[0][0]
	arr2Min[N - 1] = arr[N - 1][1]
	arr2Max[N - 1] = arr[N - 1][1]
	for i in range(1, N):
		arr1Min[i] = min(arr1Min[i - 1], arr[i][0])
		arr1Max[i] = max(arr1Min[i - 1], arr[i][0])
	for i in range(N - 2, -1, -1):
		arr2Min[i] = min(arr2Min[i + 1], arr[i][1])
		arr2Max[i] = max(arr2Max[i + 1], arr[i][1])
	ans = arr[N - 1][0] - arr[0][0]
	for i in range(N - 1, -1, -1):
		if i == 0:
			maximum = arr2Max[0]
			minimum = arr2Min[0]
		else:
			maximum = max(arr1Max[i - 1], arr2Max[i])
			minimum = min(arr1Min[i - 1], arr2Min[i])
		ans = min(ans, maximum - minimum)
	print(ans)


import math
case = int(input())
for _ in range(case):
	n = int(input())
	l1 = list(map(int, input().split(' ')))
	l2 = list(map(int, input().split(' ')))
	for i in range(n):
		if l1[i] > l2[i]:
			(l1[i], l2[i]) = (l2[i], l1[i])
	arr = [[l1[i], l2[i]] for i in range(n)]
	arr.sort()
	lrmin = [0] * n
	lrmax = [0] * n
	lrmin[0] = arr[0][1]
	lrmax[0] = arr[0][1]
	rlmin = [0] * n
	rlmax = [0] * n
	rlmin[-1] = arr[-1][0]
	rlmax[-1] = arr[-1][0]
	for i in range(1, n):
		lrmin[i] = min(lrmin[i - 1], arr[i][1])
		lrmax[i] = max(lrmax[i - 1], arr[i][1])
	for i in range(n - 2, -1, -1):
		rlmin[i] = min(rlmin[i + 1], arr[i][0])
		rlmax[i] = max(rlmax[i + 1], arr[i][0])
	res = arr[-1][0] - arr[0][0]
	for i in range(1, n):
		mn = min(lrmin[i - 1], rlmin[i])
		mx = max(lrmax[i - 1], rlmax[i])
		res = min(res, mx - mn)
	res = min(res, lrmax[n - 1] - lrmin[n - 1])
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	for i in range(n):
		c.append([min(a[i], b[i]), i])
		c.append([max(a[i], b[i]), i])
	c.sort()
	(ans, ptr) = (10 ** 10, 0)
	last = [-1] * n
	have = 0
	for i in range(2 * n):
		(val, id) = c[i]
		if last[id] == -1:
			have += 1
		last[id] = i
		if have < n:
			continue
		while True:
			if last[c[ptr][1]] == ptr:
				break
			ptr += 1
		ans = min(ans, c[i][0] - c[ptr][0])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if n == 1:
		print(0)
	elif n == 2:
		print(min(abs(a[1] - a[0]), abs(b[1] - a[0]), abs(a[1] - b[0]), abs(b[1] - b[0])))
	else:
		els = []
		for i in range(n):
			els.append((a[i], i))
			els.append((b[i], i))
		els.sort()
		doubs = {}
		elids = {}
		for i in range(2 * n):
			e = els[i][1]
			if e in doubs:
				doubs[e].append(i)
			else:
				doubs[e] = [i]
			elids[i] = e
		mindist = float('inf')
		ri = 0
		li = 0
		en = set()
		while li < 2 * n:
			while len(en) < n and ri < 2 * n:
				en.add(els[ri][1])
				ri += 1
			if els[ri - 1][0] - els[li][0] < mindist and len(en) == n:
				mindist = els[ri - 1][0] - els[li][0]
			if doubs[els[li][1]][1] >= ri or doubs[els[li][1]][1] <= li:
				en.remove(els[li][1])
			li += 1
		print(mindist)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	C = list()
	for i in range(N):
		C.append([A[i], i])
		C.append([B[i], i])
	C.sort(key=lambda x: x[0])
	ans = 10 ** 10
	last = [-1] * N
	p = 0
	num = 0
	for i in range(2 * N):
		(val, ind) = C[i]
		if last[ind] == -1:
			num += 1
		last[ind] = i
		if num < N:
			continue
		while True:
			if last[C[p][1]] == p:
				break
			p += 1
		ans = min(ans, C[i][0] - C[p][0])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	for i in range(n):
		if arr[i] < brr[i]:
			(arr[i], brr[i]) = (brr[i], arr[i])
	crr = []
	for i in range(n):
		crr.append([arr[i], brr[i]])
	crr.sort()
	maxi = crr[n - 1][0]
	mini = crr[0][0]
	ans = maxi - mini
	fmini = [None] * n
	fmaxi = [None] * n
	lmini = [None] * n
	lmaxi = [None] * n
	fmini[0] = crr[0][0]
	fmaxi[0] = crr[0][0]
	lmini[n - 1] = crr[n - 1][1]
	lmaxi[n - 1] = crr[n - 1][1]
	for i in range(1, n):
		fmini[i] = min(fmini[i - 1], crr[i][0])
		fmaxi[i] = max(fmaxi[i - 1], crr[i][0])
	i = n - 2
	while i >= 0:
		lmini[i] = min(lmini[i + 1], crr[i][1])
		lmaxi[i] = max(lmaxi[i + 1], crr[i][1])
		i -= 1
	i = n - 1
	while i >= 0:
		(crr[i][0], crr[i][1]) = (crr[i][1], crr[i][0])
		if i == 0:
			maxi = lmaxi[0]
			mini = lmini[0]
		else:
			maxi = max(fmaxi[i - 1], lmaxi[i])
			mini = min(fmini[i - 1], lmini[i])
		ans = min(ans, maxi - mini)
		i -= 1
	print(ans)


t = int(input())
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	for i in range(n):
		if a[i] < b[i]:
			(a[i], b[i]) = (b[i], a[i])
	twoD = [[a[i], b[i]] for i in range(n)]
	twoD.sort()
	maximum = twoD[n - 1][0]
	minimum = twoD[0][0]
	res = maximum - minimum
	firstMin = [0] * n
	firstMax = [0] * n
	lastMin = [0] * n
	lastMax = [0] * n
	firstMin[0] = twoD[0][0]
	lastMin[n - 1] = twoD[n - 1][1]
	firstMax[0] = twoD[0][0]
	lastMax[n - 1] = twoD[n - 1][1]
	for i in range(1, n):
		firstMin[i] = min(firstMin[i - 1], twoD[i][0])
		firstMax[i] = max(firstMax[i - 1], twoD[i][0])
	for i in range(n - 2, -1, -1):
		lastMin[i] = min(lastMin[i + 1], twoD[i][1])
		lastMax[i] = max(lastMax[i + 1], twoD[i][1])
	for i in range(n - 1, -1, -1):
		(twoD[i][0], twoD[i][1]) = (twoD[i][1], twoD[i][0])
		if i == 0:
			maximum = lastMax[0]
			minimum = lastMin[0]
		else:
			maximum = max(firstMax[i - 1], lastMax[i])
			minimum = min(firstMin[i - 1], lastMin[i])
		res = min(res, maximum - minimum)
	print(res)
	t -= 1


def solution(n, a, b):
	res = []
	for i in range(n):
		if a[i] < b[i]:
			(a[i], b[i]) = (b[i], a[i])
	l = [[a[i], b[i]] for i in range(n)]
	l.sort()
	mx = l[n - 1][0]
	mn = l[0][0]
	res.append(mx - mn)
	l1 = [0] * n
	l2 = [0] * n
	l_Min = [0] * n
	l_Max = [0] * n
	l1[0] = l[0][0]
	l_Min[n - 1] = l[n - 1][1]
	l2[0] = l[0][0]
	l_Max[n - 1] = l[n - 1][1]
	for i in range(1, n):
		l1[i] = min(l1[i - 1], l[i][0])
		l2[i] = max(l2[i - 1], l[i][0])
	for i in range(n - 2, -1, -1):
		l_Min[i] = min(l_Min[i + 1], l[i][1])
		l_Max[i] = max(l_Max[i + 1], l[i][1])
	for i in range(n - 1, -1, -1):
		(l[i][0], l[i][1]) = (l[i][1], l[i][0])
		if i == 0:
			mx = l_Max[0]
			mn = l_Min[0]
		else:
			mx = max(l2[i - 1], l_Max[i])
			mn = min(l1[i - 1], l_Min[i])
		res[-1] = min(res[-1], mx - mn)
	return min(res)
	l
t = int(input())
for _ in range(t):
	n = int(input())
	a1 = list(map(int, input().split()))
	a2 = list(map(int, input().split()))
	print(solution(n, a1, a2))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = []
	for i in range(n):
		if a[i] < b[i]:
			(a[i], b[i]) = (b[i], a[i])
		c.append([a[i], b[i]])
	c.sort()
	fMin = [0] * n
	fMax = [0] * n
	lMin = [0] * n
	lMax = [0] * n
	fMax[0] = c[0][0]
	fMin[0] = c[0][0]
	lMax[-1] = c[-1][1]
	lMin[-1] = c[-1][1]
	for i in range(1, n):
		fMin[i] = min(fMin[i - 1], c[i][0])
		fMax[i] = max(fMax[i - 1], c[i][0])
	for i in range(n - 2, -1, -1):
		lMin[i] = min(lMin[i + 1], c[i][1])
		lMax[i] = max(lMax[i + 1], c[i][1])
	mx = c[-1][0]
	mn = c[0][0]
	ans = mx - mn
	for i in range(n - 1, -1, -1):
		if not i:
			mx = lMax[0]
			mn = lMin[0]
		else:
			mx = max(fMax[i - 1], lMax[i])
			mn = min(fMin[i - 1], lMin[i])
		ans = min(ans, mx - mn)
	print(ans)


def solve(n, a, b):
	ans = []
	for i in range(n):
		if a[i] < b[i]:
			(a[i], b[i]) = (b[i], a[i])
	kunal = [[a[i], b[i]] for i in range(n)]
	kunal.sort()
	mvaskunx = kunal[n - 1][0]
	uimm = kunal[0][0]
	ans.append(mvaskunx - uimm)
	twer1 = [0] * n
	x2 = [0] * n
	lastMin = [0] * n
	lastMax = [0] * n
	twer1[0] = kunal[0][0]
	lastMin[n - 1] = kunal[n - 1][1]
	x2[0] = kunal[0][0]
	lastMax[n - 1] = kunal[n - 1][1]
	for i in range(1, n):
		twer1[i] = min(twer1[i - 1], kunal[i][0])
		x2[i] = max(x2[i - 1], kunal[i][0])
	for i in range(n - 2, -1, -1):
		lastMin[i] = min(lastMin[i + 1], kunal[i][1])
		lastMax[i] = max(lastMax[i + 1], kunal[i][1])
	for i in range(n - 1, -1, -1):
		(kunal[i][0], kunal[i][1]) = (kunal[i][1], kunal[i][0])
		if i == 0:
			mvaskunx = lastMax[0]
			uimm = lastMin[0]
		else:
			mvaskunx = max(x2[i - 1], lastMax[i])
			uimm = min(twer1[i - 1], lastMin[i])
		ans[-1] = min(ans[-1], mvaskunx - uimm)
	return min(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	print(solve(n, arr1, arr2))


def func(n, x, y):
	ans = []
	for i in range(n):
		if x[i] < y[i]:
			(x[i], y[i]) = (y[i], x[i])
	set = [[x[i], y[i]] for i in range(n)]
	set.sort()
	maxvar = set[n - 1][0]
	minvar = set[0][0]
	ans.append(maxvar - minvar)
	a = [0] * n
	b = [0] * n
	lastMin = [0] * n
	lastMax = [0] * n
	a[0] = set[0][0]
	lastMin[n - 1] = set[n - 1][1]
	b[0] = set[0][0]
	lastMax[n - 1] = set[n - 1][1]
	for i in range(1, n):
		a[i] = min(a[i - 1], set[i][0])
		b[i] = max(b[i - 1], set[i][0])
	for i in range(n - 2, -1, -1):
		lastMin[i] = min(lastMin[i + 1], set[i][1])
		lastMax[i] = max(lastMax[i + 1], set[i][1])
	for i in range(n - 1, -1, -1):
		(set[i][0], set[i][1]) = (set[i][1], set[i][0])
		if i == 0:
			mx = lastMax[0]
			mn = lastMin[0]
		else:
			mx = max(b[i - 1], lastMax[i])
			mn = min(a[i - 1], lastMin[i])
		ans[-1] = min(ans[-1], mx - mn)
	return min(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	print(func(n, arr1, arr2))


def solve(n, a, b):
	ans = []
	for i in range(n):
		if a[i] < b[i]:
			(a[i], b[i]) = (b[i], a[i])
	tup = [[a[i], b[i]] for i in range(n)]
	tup.sort()
	maxx = tup[n - 1][0]
	minn = tup[0][0]
	ans.append(maxx - minn)
	y1 = [0] * n
	y2 = [0] * n
	lastMinn = [0] * n
	lastMaxx = [0] * n
	y1[0] = tup[0][0]
	lastMinn[n - 1] = tup[n - 1][1]
	y2[0] = tup[0][0]
	lastMaxx[n - 1] = tup[n - 1][1]
	for i in range(1, n):
		y1[i] = min(y1[i - 1], tup[i][0])
		y2[i] = max(y2[i - 1], tup[i][0])
	for i in range(n - 2, -1, -1):
		lastMinn[i] = min(lastMinn[i + 1], tup[i][1])
		lastMaxx[i] = max(lastMaxx[i + 1], tup[i][1])
	for i in range(n - 1, -1, -1):
		(tup[i][0], tup[i][1]) = (tup[i][1], tup[i][0])
		if i == 0:
			maxx = lastMaxx[0]
			minn = lastMinn[0]
		else:
			maxx = max(y2[i - 1], lastMaxx[i])
			minn = min(y1[i - 1], lastMinn[i])
		ans[-1] = min(ans[-1], maxx - minn)
	return min(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	print(solve(n, arr1, arr2))


def solve(n, a, b):
	ret = []
	for i in range(n):
		if a[i] < b[i]:
			(a[i], b[i]) = (b[i], a[i])
	tup = [[a[i], b[i]] for i in range(n)]
	tup.sort()
	mx = tup[n - 1][0]
	mn = tup[0][0]
	ret.append(mx - mn)
	x1 = [0] * n
	x2 = [0] * n
	prevMin = [0] * n
	prevMax = [0] * n
	x1[0] = tup[0][0]
	prevMin[n - 1] = tup[n - 1][1]
	x2[0] = tup[0][0]
	prevMax[n - 1] = tup[n - 1][1]
	for i in range(1, n):
		x1[i] = min(x1[i - 1], tup[i][0])
		x2[i] = max(x2[i - 1], tup[i][0])
	for i in range(n - 2, -1, -1):
		prevMin[i] = min(prevMin[i + 1], tup[i][1])
		prevMax[i] = max(prevMax[i + 1], tup[i][1])
	for i in range(n - 1, -1, -1):
		(tup[i][0], tup[i][1]) = (tup[i][1], tup[i][0])
		if i == 0:
			mx = prevMax[0]
			mn = prevMin[0]
		else:
			mx = max(x2[i - 1], prevMax[i])
			mn = min(x1[i - 1], prevMin[i])
		ret[-1] = min(ret[-1], mx - mn)
	return min(ret)
t = int(input())
for _ in range(t):
	n = int(input())
	UpperArr = list(map(int, input().split()))
	LowerArr = list(map(int, input().split()))
	print(solve(n, UpperArr, LowerArr))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	brr = list(map(int, input().split(' ')))
	for (idx, (val1, val2)) in enumerate(zip(arr, brr)):
		if val1 < val2:
			arr[idx] = val2
			brr[idx] = val1
	combined = []
	for (idx, (val1, val2)) in enumerate(zip(arr, brr)):
		curr = [val1, val2]
		combined.append(curr)
	combined.sort()
	firstMn = [0 for _ in range(n)]
	firstMx = [0 for _ in range(n)]
	lastMn = [0 for _ in range(n)]
	lastMx = [0 for _ in range(n)]
	firstMn[0] = combined[0][0]
	firstMx[0] = combined[0][0]
	lastMn[n - 1] = combined[n - 1][1]
	lastMx[n - 1] = combined[n - 1][1]
	for i in range(1, n):
		firstMn[i] = min(firstMn[i - 1], combined[i][0])
		firstMx[i] = max(firstMx[i - 1], combined[i][0])
	for i in range(n - 2, -1, -1):
		lastMn[i] = min(lastMn[i + 1], combined[i][1])
		lastMx[i] = max(lastMx[i + 1], combined[i][1])
	ans = combined[n - 1][0] - combined[0][0]
	for i in range(n - 1, -1, -1):
		if i == 0:
			mx = lastMx[i]
			mn = lastMn[i]
		else:
			mx = max(firstMx[i - 1], lastMx[i])
			mn = min(firstMn[i - 1], lastMn[i])
		ans = min(ans, mx - mn)
	print(ans)


import sys
from typing import List, Tuple

def min_difference(t: int, t1: List[Tuple[int, List[int], List[int]]]) -> List[int]:
	op = []
	for i in range(t):
		n = t1[i][0]
		arr = t1[i][1]
		brr = t1[i][2]
		for i in range(n):
			if arr[i] < brr[i]:
				(arr[i], brr[i]) = (brr[i], arr[i])
		combined = [[arr[i], brr[i]] for i in range(n)]
		combined.sort()
		m1 = combined[n - 1][0]
		m2 = combined[0][0]
		op.append(m1 - m2)
		firstMin = [0] * n
		firstMax = [0] * n
		lastMin = [0] * n
		lastMax = [0] * n
		firstMin[0] = combined[0][0]
		lastMin[n - 1] = combined[n - 1][1]
		firstMax[0] = combined[0][0]
		lastMax[n - 1] = combined[n - 1][1]
		for i in range(1, n):
			firstMin[i] = min(firstMin[i - 1], combined[i][0])
			firstMax[i] = max(firstMax[i - 1], combined[i][0])
		for i in range(n - 2, -1, -1):
			lastMin[i] = min(lastMin[i + 1], combined[i][1])
			lastMax[i] = max(lastMax[i + 1], combined[i][1])
		for i in range(n - 1, -1, -1):
			(combined[i][0], combined[i][1]) = (combined[i][1], combined[i][0])
			if i == 0:
				m1 = lastMax[0]
				m2 = lastMin[0]
			else:
				m1 = max(firstMax[i - 1], lastMax[i])
				m2 = min(firstMin[i - 1], lastMin[i])
			op[-1] = min(op[-1], m1 - m2)
	return op
t = int(input())
t1 = []
for _ in range(t):
	q = int(input())
	x = list(map(int, input().split()))
	y = list(map(int, input().split()))
	t1.append((q, x, y))
op = min_difference(t, t1)
for i in op:
	print(i)


import sys
from typing import List, Tuple

def min_diff(t: int, test_cases: List[Tuple[int, List[int], List[int]]]) -> List[int]:
	res = []
	for i in range(t):
		n = test_cases[i][0]
		a = test_cases[i][1]
		b = test_cases[i][2]
		for i in range(n):
			if a[i] < b[i]:
				(a[i], b[i]) = (b[i], a[i])
		c = [[a[i], b[i]] for i in range(n)]
		c.sort()
		mx = c[n - 1][0]
		mn = c[0][0]
		res.append(mx - mn)
		fmi = [0] * n
		fmx = [0] * n
		lmi = [0] * n
		lmx = [0] * n
		fmi[0] = c[0][0]
		lmi[n - 1] = c[n - 1][1]
		fmx[0] = c[0][0]
		lmx[n - 1] = c[n - 1][1]
		for i in range(1, n):
			fmi[i] = min(fmi[i - 1], c[i][0])
			fmx[i] = max(fmx[i - 1], c[i][0])
		for i in range(n - 2, -1, -1):
			lmi[i] = min(lmi[i + 1], c[i][1])
			lmx[i] = max(lmx[i + 1], c[i][1])
		for i in range(n - 1, -1, -1):
			(c[i][0], c[i][1]) = (c[i][1], c[i][0])
			if i == 0:
				mx = lmx[0]
				mn = lmi[0]
			else:
				mx = max(fmx[i - 1], lmx[i])
				mn = min(fmi[i - 1], lmi[i])
			res[-1] = min(res[-1], mx - mn)
	return res
t = int(input())
test_cases = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	test_cases.append((n, a, b))
ans = min_diff(t, test_cases)
for i in ans:
	print(i)


def solve(n, a, b):
	ans = []
	for i in range(n):
		if a[i] < b[i]:
			(a[i], b[i]) = (b[i], a[i])
	tup = [[a[i], b[i]] for i in range(n)]
	tup.sort()
	mx = tup[n - 1][0]
	mn = tup[0][0]
	ans.append(mx - mn)
	x1 = [0] * n
	x2 = [0] * n
	lastMin = [0] * n
	lastMax = [0] * n
	x1[0] = tup[0][0]
	lastMin[n - 1] = tup[n - 1][1]
	x2[0] = tup[0][0]
	lastMax[n - 1] = tup[n - 1][1]
	for i in range(1, n):
		x1[i] = min(x1[i - 1], tup[i][0])
		x2[i] = max(x2[i - 1], tup[i][0])
	for i in range(n - 2, -1, -1):
		lastMin[i] = min(lastMin[i + 1], tup[i][1])
		lastMax[i] = max(lastMax[i + 1], tup[i][1])
	for i in range(n - 1, -1, -1):
		(tup[i][0], tup[i][1]) = (tup[i][1], tup[i][0])
		if i == 0:
			mx = lastMax[0]
			mn = lastMin[0]
		else:
			mx = max(x2[i - 1], lastMax[i])
			mn = min(x1[i - 1], lastMin[i])
		ans[-1] = min(ans[-1], mx - mn)
	return min(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	print(solve(n, arr1, arr2))


import sys
from typing import List, Tuple

def min_difference(t: int, test_cases: List[Tuple[int, List[int], List[int]]]) -> List[int]:
	ans = []
	for i in range(t):
		n = test_cases[i][0]
		a = test_cases[i][1]
		b = test_cases[i][2]
		for i in range(n):
			if a[i] < b[i]:
				(a[i], b[i]) = (b[i], a[i])
		combined = [[a[i], b[i]] for i in range(n)]
		combined.sort()
		maximum = combined[n - 1][0]
		minimum = combined[0][0]
		ans.append(maximum - minimum)
		firstMin = [0] * n
		firstMax = [0] * n
		lastMin = [0] * n
		lastMax = [0] * n
		firstMin[0] = combined[0][0]
		lastMin[n - 1] = combined[n - 1][1]
		firstMax[0] = combined[0][0]
		lastMax[n - 1] = combined[n - 1][1]
		for i in range(1, n):
			firstMin[i] = min(firstMin[i - 1], combined[i][0])
			firstMax[i] = max(firstMax[i - 1], combined[i][0])
		for i in range(n - 2, -1, -1):
			lastMin[i] = min(lastMin[i + 1], combined[i][1])
			lastMax[i] = max(lastMax[i + 1], combined[i][1])
		for i in range(n - 1, -1, -1):
			(combined[i][0], combined[i][1]) = (combined[i][1], combined[i][0])
			if i == 0:
				maximum = lastMax[0]
				minimum = lastMin[0]
			else:
				maximum = max(firstMax[i - 1], lastMax[i])
				minimum = min(firstMin[i - 1], lastMin[i])
			ans[-1] = min(ans[-1], maximum - minimum)
	return ans
t = int(input())
test_cases = []
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	test_cases.append((n, a, b))
ans = min_difference(t, test_cases)
for i in ans:
	print(i)


for i in range(int(input())):
	N = int(input())
	arr_A = list(map(int, input().split()))
	arr_B = list(map(int, input().split()))
	for i in range(N):
		if arr_A[i] < arr_B[i]:
			(arr_A[i], arr_B[i]) = (arr_B[i], arr_A[i])
	c = [[arr_A[i], arr_B[i]] for i in range(N)]
	c.sort()
	maxB = c[N - 1][0]
	minB = c[0][0]
	soln = maxB - minB
	fminB = [0 for i in range(N)]
	fmaxB = [0 for i in range(N)]
	lminB = [0 for i in range(N)]
	lmaxB = [0 for i in range(N)]
	fminB[0] = c[0][0]
	lminB[N - 1] = c[N - 1][1]
	fmaxB[0] = c[0][0]
	lmaxB[N - 1] = c[N - 1][1]
	for i in range(1, N):
		fminB[i] = min(fminB[i - 1], c[i][0])
		fmaxB[i] = max(fmaxB[i - 1], c[i][0])
	for i in range(N - 2, -1, -1):
		lminB[i] = min(lminB[i + 1], c[i][1])
		lmaxB[i] = max(lmaxB[i + 1], c[i][1])
	for i in range(N - 1, -1, -1):
		(c[i][0], c[i][1]) = (c[i][1], c[i][0])
		if i == 0:
			maxB = lmaxB[0]
			minB = lminB[0]
		else:
			maxB = max(fmaxB[i - 1], lmaxB[i])
			minB = min(fminB[i - 1], lminB[i])
		ss = maxB - minB
		soln = min(soln, ss)
	print(soln)


for etgh in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	aa = list(a)
	bb = list(b)
	for y in range(n):
		if a[y] < b[y]:
			qweq = a[y]
			a[y] = b[y]
			b[y] = qweq
	k = []
	for t in range(n):
		k.append([a[t], b[t], t])
	k.sort()
	mn = k[0][0]
	mx = k[n - 1][0]
	ans = mx - mn
	a1 = [0 for w in range(n)]
	a2 = [0 for w in range(n)]
	b1 = [0 for w in range(n)]
	b2 = [0 for w in range(n)]
	a1[0] = k[0][0]
	a2[0] = k[0][0]
	b1[n - 1] = k[n - 1][1]
	b2[n - 1] = k[n - 1][1]
	for d in range(1, n):
		a1[d] = min(a1[d - 1], k[d][0])
		a2[d] = max(a2[d - 1], k[d][0])
	for f in range(n - 2, -1, -1):
		b1[f] = min(b1[f + 1], k[f][1])
		b2[f] = max(b2[f + 1], k[f][1])
	for g in range(n - 1, -1, -1):
		r = k[g][0]
		k[g][0] = k[g][1]
		k[g][1] = r
		if g == 0:
			maxi = b2[0]
			mini = b1[0]
		else:
			maxi = max(a2[g - 1], b2[g])
			mini = min(a1[g - 1], b1[g])
		ans = min(ans, maxi - mini)
	print(ans)


m = int(input())
for i in range(m):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for j in range(n):
		if a[j] < b[j]:
			(a[j], b[j]) = (b[j], a[j])
	c = []
	for k in range(n):
		c.append([a[k], b[k]])
	c.sort()
	maxi = c[n - 1][0]
	mini = c[0][0]
	ans = maxi - mini
	firstmin = [0] * n
	firstmax = [0] * n
	lastmin = [0] * n
	lastmax = [0] * n
	firstmin[0] = c[0][0]
	lastmin[n - 1] = c[n - 1][1]
	firstmax[0] = c[0][0]
	lastmax[n - 1] = c[n - 1][1]
	for q in range(1, n):
		firstmin[q] = min(firstmin[q - 1], c[q][0])
		firstmax[q] = max(firstmax[q - 1], c[q][0])
	for w in range(n - 2, -1, -1):
		lastmin[w] = min(lastmin[w + 1], c[w][1])
		lastmax[w] = max(lastmax[w + 1], c[w][1])
	for e in range(n - 1, -1, -1):
		(c[e][0], c[e][1]) = (c[e][1], c[e][0])
		if e == 0:
			maxi = lastmax[0]
			mini = lastmin[0]
		else:
			maxi = max(firstmax[e - 1], lastmax[e])
			mini = min(firstmin[e - 1], lastmin[e])
		ans = min(ans, maxi - mini)
	print(ans)


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()]
	for i in range(n):
		if A[i] < B[i]:
			tmp = A[i]
			A[i] = B[i]
			B[i] = tmp
	AB = [[-1 for i in range(2)] for i in range(n)]
	for i in range(n):
		AB[i][0] = A[i]
		AB[i][1] = B[i]
	AB.sort(key=lambda row: row[0])
	(L, R) = ([], [])
	for i in range(len(AB)):
		L.append(AB[i][0])
		R.append(AB[i][1])
	(R_max, R_min) = (max(R), min(R))
	maxi = float('-inf')
	mini = float('inf')
	for i in reversed(range(len(R))):
		maxi = max(maxi, R[i])
		mini = min(mini, R[i])
		R[i] = [mini, maxi]
	diff = min(max(L) - min(L), R_max - R_min)
	for i in range(0, n - 1):
		(L_max, R_max) = (L[n - i - 2], R[-i - 1][1])
		(L_min, R_min) = (L[0], R[-i - 1][0])
		A_max = max(L_max, R_max)
		A_min = min(L_min, R_min)
		diff = min(diff, A_max - A_min)
	print(diff)


def swap(A, B, i):
	(A[i], B[i]) = (B[i], A[i])

def solution(A, B, n):
	for i in range(n):
		if A[i] < B[i]:
			swap(A, B, i)
	combined = [[0 for i in range(2)] for j in range(n)]
	for i in range(n):
		combined[i][0] = A[i]
		combined[i][1] = B[i]
	combined.sort(key=lambda x: x[0])
	maxx = combined[n - 1][0]
	minn = combined[0][0]
	ans = maxx - minn
	firstmin = [0] * n
	firstmax = [0] * n
	lastmin = [0] * n
	lastmax = [0] * n
	firstmin[0] = combined[0][0]
	lastmin[n - 1] = combined[n - 1][1]
	firstmax[0] = combined[0][0]
	lastmax[n - 1] = combined[n - 1][1]
	for i in range(1, n):
		firstmin[i] = min(firstmin[i - 1], combined[i][0])
		firstmax[i] = max(firstmax[i - 1], combined[i][0])
	for i in range(n - 2, -1, -1):
		lastmin[i] = min(lastmin[i + 1], combined[i][1])
		lastmax[i] = max(lastmax[i + 1], combined[i][1])
	for i in range(n - 1, -1, -1):
		(combined[i][0], combined[i][1]) = (combined[i][1], combined[i][0])
		if i == 0:
			maxx = lastmax[0]
			minn = lastmin[0]
		else:
			maxx = max(firstmax[i - 1], lastmax[i])
			minn = min(firstmin[i - 1], lastmin[i])
		ans = min(ans, maxx - minn)
	print(ans)
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	solution(A, B, n)


T = int(input())
for _ in range(T):
	N = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	for i in range(N):
		if arr1[i] < arr2[i]:
			(arr1[i], arr2[i]) = (arr2[i], arr1[i])
	combined_arr = [[arr1[i], arr2[i]] for i in range(N)]
	combined_arr.sort()
	max_val = combined_arr[N - 1][0]
	min_val = combined_arr[0][0]
	ans = max_val - min_val
	first_min = [0] * N
	first_max = [0] * N
	last_min = [0] * N
	last_max = [0] * N
	first_min[0] = combined_arr[0][0]
	last_min[N - 1] = combined_arr[N - 1][1]
	first_max[0] = combined_arr[0][0]
	last_max[N - 1] = combined_arr[N - 1][1]
	for i in range(1, N):
		first_min[i] = min(first_min[i - 1], combined_arr[i][0])
		first_max[i] = max(first_max[i - 1], combined_arr[i][0])
	for i in range(N - 2, -1, -1):
		last_min[i] = min(last_min[i + 1], combined_arr[i][1])
		last_max[i] = max(last_max[i + 1], combined_arr[i][1])
	for i in range(N - 1, -1, -1):
		(combined_arr[i][0], combined_arr[i][1]) = (combined_arr[i][1], combined_arr[i][0])
		if i == 0:
			max_val = last_max[0]
			min_val = last_min[0]
		else:
			max_val = max(first_max[i - 1], last_max[i])
			min_val = min(first_min[i - 1], last_min[i])
		ans = min(ans, max_val - min_val)
	print(ans)


for i in range(int(input())):
	num_elements = int(input())
	array1 = list(map(int, input().split()))
	array2 = list(map(int, input().split()))
	for i in range(num_elements):
		if array1[i] < array2[i]:
			(array1[i], array2[i]) = (array2[i], array1[i])
	combined_array = [[array1[i], array2[i]] for i in range(num_elements)]
	combined_array.sort()
	max_element = combined_array[num_elements - 1][0]
	min_element = combined_array[0][0]
	result = max_element - min_element
	first_min_array = [0] * num_elements
	first_max_array = [0] * num_elements
	last_min_array = [0] * num_elements
	last_max_array = [0] * num_elements
	first_min_array[0] = combined_array[0][0]
	last_min_array[num_elements - 1] = combined_array[num_elements - 1][1]
	first_max_array[0] = combined_array[0][0]
	last_max_array[num_elements - 1] = combined_array[num_elements - 1][1]
	for i in range(1, num_elements):
		first_min_array[i] = min(first_min_array[i - 1], combined_array[i][0])
		first_max_array[i] = max(first_max_array[i - 1], combined_array[i][0])
	for i in range(num_elements - 2, -1, -1):
		last_min_array[i] = min(last_min_array[i + 1], combined_array[i][1])
		last_max_array[i] = max(last_max_array[i + 1], combined_array[i][1])
	for i in range(num_elements - 1, -1, -1):
		(combined_array[i][0], combined_array[i][1]) = (combined_array[i][1], combined_array[i][0])
		if i == 0:
			max_element = last_max_array[0]
			min_element = last_min_array[0]
		else:
			max_element = max(first_max_array[i - 1], last_max_array[i])
			min_element = min(first_min_array[i - 1], last_min_array[i])
		result = min(result, max_element - min_element)
	print(result)


lm = int(input())
while lm > 0:
	nb = int(input())
	ab = list(map(int, input().split()))
	bb = list(map(int, input().split()))
	for ib in range(nb):
		if ab[ib] < bb[ib]:
			(ab[ib], bb[ib]) = (bb[ib], ab[ib])
	combined = []
	for ib in range(nb):
		combined.append([ab[ib], bb[ib]])
	combined.sort()
	maximumb = combined[nb - 1][0]
	minimumb = combined[0][0]
	ansb = maximumb - minimumb
	firstMinb = [0] * nb
	firstMaxb = [0] * nb
	lastMinb = [0] * nb
	lastMaxb = [0] * nb
	firstMinb[0] = combined[0][0]
	lastMinb[nb - 1] = combined[nb - 1][1]
	firstMaxb[0] = combined[0][0]
	lastMaxb[nb - 1] = combined[nb - 1][1]
	for ib in range(1, nb):
		firstMinb[ib] = min(firstMinb[ib - 1], combined[ib][0])
		firstMaxb[ib] = max(firstMaxb[ib - 1], combined[ib][0])
	for ib in range(nb - 2, -1, -1):
		lastMinb[ib] = min(lastMinb[ib + 1], combined[ib][1])
		lastMaxb[ib] = max(lastMaxb[ib + 1], combined[ib][1])
	for ib in range(nb - 1, -1, -1):
		(combined[ib][0], combined[ib][1]) = (combined[ib][1], combined[ib][0])
		if ib == 0:
			maximumb = lastMaxb[0]
			minimumb = lastMinb[0]
		else:
			maximumb = max(firstMaxb[ib - 1], lastMaxb[ib])
			minimumb = min(firstMinb[ib - 1], lastMinb[ib])
		ansb = min(ansb, maximumb - minimumb)
	print(ansb)
	lm -= 1


from sys import stdin, stdout
from heapq import heapify, heappop, heappush
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	l1 = list(map(int, stdin.readline().split()))
	l2 = list(map(int, stdin.readline().split()))
	l = []
	for i in range(n):
		k = [l1[i], l2[i]]
		k.sort()
		l.append(k)
	l.sort()
	h = []
	heapify(h)
	maxi = 0
	for i in range(n):
		a = l[i]
		heappush(h, [a[0], i])
		maxi = max(maxi, a[0])
	temp = heappop(h)
	ans = maxi - temp[0]
	heappush(h, temp)
	for i in range(n):
		a = heappop(h)
		heappush(h, [l[a[1]][1], 10 ** 10])
		maxi = max(maxi, l[a[1]][1])
		temp = heappop(h)
		ans = min(ans, maxi - temp[0])
		heappush(h, temp)
		if temp[1] != i + 1:
			break
	print(ans)


import numpy as np
T = int(input())
while T != 0:
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	pairs = []
	for i in range(len(l1)):
		if l1[i] < l2[i]:
			(l1[i], l2[i]) = (l2[i], l1[i])
	for i in range(len(l1)):
		pairs.append([l1[i], l2[i]])
	pairs = np.array(pairs)
	pairs = pairs[pairs[:, 0].argsort()]
	high = pairs[-1][0]
	low = pairs[0][0]
	ans = high - low
	(fmax, fmin, lmax, lmin) = ([0 for i in range(n)], [0 for i in range(n)], [0 for i in range(n)], [0 for i in range(n)])
	fmin[0] = int(pairs[0][0])
	lmin[n - 1] = int(pairs[n - 1][1])
	fmax[0] = int(pairs[0][0])
	lmax[n - 1] = int(pairs[n - 1][1])
	for i in range(1, n):
		fmin[i] = min(fmin[i - 1], int(pairs[i][0]))
		fmax[i] = max(fmax[i - 1], int(pairs[i][0]))
	for i in range(n - 2, -1, -1):
		lmin[i] = min(lmin[i + 1], int(pairs[i][1]))
		lmax[i] = max(lmax[i + 1], int(pairs[i][1]))
	for i in range(n - 1, -1, -1):
		(pairs[i][0], pairs[i][1]) = (pairs[i][1], pairs[i][0])
		if i == 0:
			high = lmax[0]
			low = lmin[0]
		else:
			high = max(fmax[i - 1], lmax[i])
			low = min(fmin[i - 1], lmin[i])
		ans = min(ans, high - low)
	print(ans)
	T -= 1


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	for i in range(n):
		if arr[i] < brr[i]:
			(arr[i], brr[i]) = (brr[i], arr[i])
	merge = []
	for i in range(n):
		merge.append([arr[i], brr[i]])
	merge.sort()
	maximum = merge[n - 1][0]
	minimum = merge[0][0]
	result = maximum - minimum
	first_Min = [0] * n
	first_Max = [0] * n
	last_Min = [0] * n
	last_Max = [0] * n
	first_Min[0] = merge[0][0]
	last_Min[n - 1] = merge[n - 1][1]
	first_Max[0] = merge[0][0]
	last_Max[n - 1] = merge[n - 1][1]
	for i in range(1, n):
		first_Min[i] = min(first_Min[i - 1], merge[i][0])
		first_Max[i] = max(first_Max[i - 1], merge[i][0])
	for i in range(n - 2, -1, -1):
		last_Min[i] = min(last_Min[i + 1], merge[i][1])
		last_Max[i] = max(last_Max[i + 1], merge[i][1])
	for i in range(n - 1, -1, -1):
		(merge[i][0], merge[i][1]) = (merge[i][1], merge[i][0])
		if i == 0:
			maximum = last_Max[0]
			minimum = last_Min[0]
		else:
			maximum = max(first_Max[i - 1], last_Max[i])
			minimum = min(first_Min[i - 1], last_Min[i])
		result = min(result, maximum - minimum)
	print(result)
	t -= 1


t = int(input())
for k in range(t):
	n = int(input())
	a = [int(numa) for numa in input().split()]
	b = [int(numb) for numb in input().split()]
	for j in range(n):
		if a[j] < b[j]:
			temp = a[j]
			a[j] = b[j]
			b[j] = temp
	c = []
	for j in range(n):
		l = []
		l.append(a[j])
		l.append(b[j])
		c.append(l)
	c.sort()
	maximum = c[n - 1][0]
	minimum = c[0][0]
	ans = maximum - minimum
	fmin = [0] * n
	fmax = [0] * n
	lmin = [0] * n
	lmax = [0] * n
	fmin[0] = c[0][0]
	lmin[n - 1] = c[n - 1][1]
	fmax[0] = c[0][0]
	lmax[n - 1] = c[n - 1][1]
	for i in range(1, n):
		fmin[i] = min(fmin[i - 1], c[i][0])
		fmax[i] = max(fmax[i - 1], c[i][0])
	for i in range(n - 2, -1, -1):
		lmin[i] = min(lmin[i + 1], c[i][1])
		lmax[i] = max(lmax[i + 1], c[i][1])
	for i in range(n - 1, -1, -1):
		temp = c[i][0]
		c[i][0] = c[i][1]
		c[i][1] = temp
		if i == 0:
			maximum = lmax[0]
			minimum = lmin[0]
		else:
			maximum = max(fmax[i - 1], lmax[i])
			minimum = min(fmin[i - 1], lmin[i])
		ans = min(ans, maximum - minimum)
	print(ans)


def main():
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	for i in range(N):
		if A[i] < B[i]:
			temp = A[i]
			A[i] = B[i]
			B[i] = temp
	combined = []
	for i in range(N):
		combined.append([A[i], B[i]])
	combined = sorted(combined, key=lambda x: x[0])
	MAX = combined[N - 1][0]
	MIN = combined[0][0]
	ans = MAX - MIN
	(firstMin, firstMax, lastMin, lastMax) = ([0] * N, [0] * N, [0] * N, [0] * N)
	firstMin[0] = combined[0][0]
	lastMin[N - 1] = combined[N - 1][1]
	firstMax[0] = combined[0][0]
	lastMax[N - 1] = combined[N - 1][1]
	for i in range(1, N):
		firstMin[i] = min(firstMin[i - 1], combined[i][0])
		firstMax[i] = max(firstMax[i - 1], combined[i][0])
	for i in range(N - 2, -1, -1):
		lastMin[i] = min(lastMin[i + 1], combined[i][1])
		lastMax[i] = max(lastMax[i + 1], combined[i][1])
	for i in range(N - 1, -1, -1):
		temp = combined[i][0]
		combined[i][0] = combined[i][1]
		combined[i][1] = temp
		if i == 0:
			MAX = lastMax[0]
			MIN = lastMin[0]
		else:
			MAX = max(firstMax[i - 1], lastMax[i])
			MIN = min(firstMin[i - 1], lastMin[i])
		ans = min(ans, MAX - MIN)
	return ans
for _ in range(int(input())):
	print(main())


import math
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 = [[0 for i in range(2)] for j in range(n)]
	for i in range(n):
		C[i][0] = A[i]
		C[i][1] = B[i]
	for i in range(n):
		if C[i][0] < C[i][1]:
			(C[i][0], C[i][1]) = (C[i][1], C[i][0])
	C.sort()
	max1 = C[n - 1][0]
	min1 = C[0][0]
	ans = max1 - min1
	fMin = [0] * n
	fMax = [0] * n
	lMin = [0] * n
	lMax = [0] * n
	fMin[0] = C[0][0]
	lMin[n - 1] = C[n - 1][1]
	fMax[0] = C[0][0]
	lMax[n - 1] = C[n - 1][1]
	for i in range(1, n):
		fMin[i] = min(fMin[i - 1], C[i][0])
		fMax[i] = max(fMax[i - 1], C[i][0])
	for i in range(n - 2, -1, -1):
		lMin[i] = min(lMin[i + 1], C[i][1])
		lMax[i] = max(lMax[i + 1], C[i][1])
	for i in range(n - 1, -1, -1):
		(C[i][0], C[i][1]) = (C[i][1], C[i][0])
		if i == 0:
			max1 = lMax[0]
			min1 = lMin[0]
		else:
			max1 = max(fMax[i - 1], lMax[i])
			min1 = min(fMin[i - 1], lMin[i])
		ans = min(ans, max1 - min1)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		if a[i] < b[i]:
			(a[i], b[i]) = (b[i], a[i])
	co = list(sorted(zip(a, b)))
	c = [list(i) for i in co]
	res = c[n - 1][0] - c[0][0]
	firstMin = [c[0][0]] * n
	firstMax = [c[0][0]] * n
	lastMin = [c[n - 1][1]] * n
	lastMax = [c[n - 1][1]] * n
	for i in range(1, n):
		firstMin[i] = min(firstMin[i - 1], c[i][0])
		firstMax[i] = max(firstMax[i - 1], c[i][0])
	for i in range(n - 2, -1, -1):
		lastMin[i] = min(lastMin[i + 1], c[i][1])
		lastMax[i] = max(lastMax[i + 1], c[i][1])
	for i in range(n - 1, -1, -1):
		if i == 0:
			mx = lastMax[0]
			mn = lastMin[0]
		else:
			mx = max(firstMax[i - 1], lastMax[i])
			mn = min(firstMin[i - 1], lastMin[i])
		res = min(res, mx - mn)
	print(res)


for _ in range(int(input())):
	n = int(input())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	for i in range(n):
		if A[i] < B[i]:
			(A[i], B[i]) = (B[i], A[i])
	C = [[0, 0] for x in range(n)]
	for i in range(n):
		C[i][0] = A[i]
		C[i][1] = B[i]
	C = sorted(C, key=lambda l: l[0])
	(maxC, minC) = (C[n - 1][0], C[0][0])
	delta = maxC - minC
	helper1 = [0 for x in range(n)]
	helper2 = [0 for x in range(n)]
	helper1B = [0 for x in range(n)]
	helper2B = [0 for x in range(n)]
	(helper1[0], helper2[n - 1], helper1B[0], helper2B[n - 1]) = (C[0][0], C[n - 1][1], C[0][0], C[n - 1][1])
	for i in range(1, n):
		helper1[i] = min(helper1[i - 1], C[i][0])
		helper1B[i] = max(helper1B[i - 1], C[i][0])
	for i in range(n - 2, -1, -1):
		helper2[i] = min(helper2[i + 1], C[i][1])
		helper2B[i] = max(helper2B[i + 1], C[i][1])
	for i in range(n - 1, -1, -1):
		(C[i][0], C[i][1]) = (C[i][1], C[i][0])
		if i == 0:
			(maxA, minA) = (helper2B[0], helper2[0])
		else:
			maxA = max(helper1B[i - 1], helper2B[i])
			minA = min(helper1[i - 1], helper2[i])
		Delta = maxA - minA
		delta = min(delta, Delta)
	print(delta)


import heapq
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	t1 = []
	maxx = max(a)
	minn = min(a)
	ans = maxx - minn
	for i in range(n):
		t1.append([-a[i], -b[i]])
	heapq.heapify(t1)
	while True:
		if ans > abs(t1[0][0]) - minn:
			ans = abs(t1[0][0]) - minn
		if abs(t1[0][0]) <= abs(t1[0][1]):
			break
		t = heapq.heappop(t1)
		(t[0], t[1]) = (t[1], t[0])
		if abs(t[0]) < minn:
			minn = abs(t[0])
		heapq.heappush(t1, t)
	maxx = abs(t1[0][0])
	for i in range(n):
		t1[i][0] = -t1[i][0]
		t1[i][1] = -t1[i][1]
		if maxx < t1[i][0]:
			maxx = t1[i][0]
	heapq.heapify(t1)
	while True:
		if ans > maxx - t1[0][0]:
			ans = maxx - t1[0][0]
		if t1[0][0] >= t1[0][1]:
			break
		t = heapq.heappop(t1)
		(t[0], t[1]) = (t[1], t[0])
		if maxx < t[0]:
			maxx = t[0]
		heapq.heappush(t1, t)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ad = a
	bd = b
	maxa = max(a)
	mina = min(a)
	maxai = a.index(maxa)
	minai = a.index(mina)
	d = a[maxai] - a[minai]
	while True:
		if bd[minai] > ad[minai]:
			temp = ad[minai]
			ad[minai] = bd[minai]
			bd[minai] = temp
		maxad = max(ad)
		minad = min(ad)
		if maxad - minad < d:
			d = maxad - minad
		if ad.index(minad) != minai:
			minai = ad.index(minad)
		else:
			break
	while True:
		if bd[maxai] < ad[maxai]:
			temp = ad[maxai]
			ad[maxai] = bd[maxai]
			bd[maxai] = temp
		maxad = max(ad)
		minad = min(ad)
		if maxad - minad < d:
			d = maxad - minad
		if ad.index(maxad) != maxai:
			maxai = ad.index(maxad)
		else:
			break
	print(d)


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	arr = [int(ele) for ele in s.strip().split()]
	s = input()
	brr = [int(ele) for ele in s.strip().split()]
	arr = arr + brr
	arr = [(arr[i], i % n) for i in range(2 * n)]
	arr.sort()
	dic = {}
	mn = 1000000001
	j = 0
	for i in range(2 * n):
		if dic.get(arr[i][1], None) == None:
			dic[arr[i][1]] = 0
		dic[arr[i][1]] += 1
		if len(dic) == n:
			while len(dic) == n:
				dic[arr[j][1]] -= 1
				if dic[arr[j][1]] == 0:
					del dic[arr[j][1]]
				j += 1
			mn = min(mn, arr[i][0] - arr[j - 1][0])
	print(mn)
	t -= 1


from heapq import heapify, heappop, heappush
T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	H = [(-x, -y) if x >= y else (-y, -x) for (x, y) in zip(a, b)]
	l = min([-x for (x, y) in H])
	heapify(H)
	ans = float('inf')
	while True:
		(x, y) = heappop(H)
		x = -x
		y = -y
		ans = min(ans, x - l)
		if y < x:
			l = min(l, y)
			heappush(H, (-y, -x))
		else:
			break
	print(ans)


for tcase in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = [(ai + bi, min(ai, bi), max(ai, bi)) for (ai, bi) in zip(a, b)]
	c.sort()
	mnb = [10 ** 9]
	for (ci, ai, bi) in c:
		mnb.append(min(mnb[-1], bi))
	mna = [10 ** 9]
	for (ci, ai, bi) in reversed(c):
		mna.append(min(mna[-1], ai))
	mna.reverse()
	mn = [min(x, y) for (x, y) in zip(mna, mnb)]
	mxb = [0]
	for (ci, ai, bi) in c:
		mxb.append(max(mxb[-1], bi))
	mxa = [0]
	for (ci, ai, bi) in reversed(c):
		mxa.append(max(mxa[-1], ai))
	mxa.reverse()
	mx = [max(x, y) for (x, y) in zip(mxa, mxb)]
	ans = [mxi - mni for (mni, mxi) in zip(mn, mx)]
	print(min(ans))


import math

def II():
	return int(input())

def LII():
	return [int(x) for x in input().split()]
for _ in range(II()):
	n = II()
	as_ = LII()
	bs_ = LII()
	items = list(enumerate(as_)) + list(enumerate(bs_))
	items.sort(key=lambda v: v[1])
	i = 0
	j = 0
	totals = n * [0]
	n_have = 0
	min_delta = math.inf
	while True:
		while j < 2 * n and n_have < n:
			if totals[items[j][0]] == 0:
				n_have += 1
			totals[items[j][0]] += 1
			j += 1
		if n_have < n:
			break
		while j < 2 * n and items[j][1] == items[j - 1][1]:
			totals[items[j][0]] += 1
			j += 1
		while totals[items[i][0]] == 2:
			totals[items[i][0]] -= 1
			i += 1
		delta = items[j - 1][1] - items[i][1]
		if delta < min_delta:
			min_delta = delta
		assert totals[items[i][0]] == 1
		totals[items[i][0]] = 0
		i += 1
		n_have -= 1
	print(min_delta)