# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* rkyouwill

*iceknight1093, tabr*

**Testers:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

Sorting

# PROBLEM:

You have two arrays A and B. In one move, you can swap any element of A with any element of B.

Find the minimum possible value of \max(A) - \min(A) that you can attain.

# EXPLANATION:

The fact that any element of A can be swapped with any element of B is quite powerful; in fact, we can pick any N integers out of the 2N we have and put them in A.

## Proof

If A already contains the N integers we want, nothing more needs to be done.

Otherwise, B contains one such integer, and A contains one integer we *don’t* want.

Swap these two, and continue.

Now, let C be an array of size 2N containing all the elements of A and B.

Let’s sort C, so C_1 \leq C_2 \leq \ldots \leq C_{2N}.

To minimize the difference, it’s clearly optimal to choose N consecutive elements from this sorted C.

That is, if the smallest element we pick is C_i, then it’s optimal to pick the elements \{C_i, C_{i+1}, \ldots, C_{i+N-1}\}; giving us a difference of C_{i+N-1} - C_i

There are N+1 choices for the smallest element: C_1, C_2, \ldots, C_{N+1}.

Try each one, compute the appropriate maximum element (C_{i+N-1}), and take their difference.

The final answer is the minimum difference among all these.

# TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

# CODE:

## Code (Python)

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