311198: CF1949B. Charming Meals

B. Charming Mealstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The Czech cuisine features $n$ appetizers and $n$ main dishes. The $i$-th appetizer has spiciness $a_i$, and the $i$-th main dish has spiciness $b_i$.

A typical Czech meal consists of exactly one appetizer and one main dish. You want to pair up the $n$ appetizers and $n$ main dishes into $n$ meals with each appetizer and each main dish being included in exactly one meal.

Your meals shall surprise the diners, so you want the spiciness levels of the two parts of the same meal to be as different as possible. The charm of a meal is the difference (in absolute value) between the spiciness of the appetizer and the spiciness of the main dish. So, a meal consisting of an appetizer with spiciness $x$ and a main dish with spiciness $y$ has charm equal to $|x-y|$.

You want to maximize the minimum charm of the resulting $n$ meals. What is the largest possible value of the minimum charm that you can achieve?

Input

Each test contains multiple test cases. The first line contains an integer $t$ ($1\le t\le 1\,000$) — the number of test cases. The descriptions of the $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 5\,000$) —the number of appetizers and main dishes.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^{9}$) — the spicinesses of the $n$ appetizers.

The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \leq b_i \leq 10^{9}$) — the spicinesses of the $n$ main dishes.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $25\cdot 10^6$.

Output

For each test case, print the largest possible value of the minimum charm you can achieve.

ExampleInput

4
3
0 0 0
1000000000 1000000000 1000000000
5
1 2 3 4 5
1 2 3 4 5
6
0 0 0 100 100 100
100 100 100 0 0 0
7
14 25 62 74 86 95 12
51 62 71 72 92 20 84

Output

1000000000
2
100
30

Note

In the first test case, no matter how you pair up the appetizers with the main dishes, each meal will have an appetizer with spiciness $0$ and a main dish with spiciness $1000000000$, so the charm of each meal will be $1000000000$.

In the second test case, one optimal way to pair up appetizers and main dishes is: $(1, 5)$, $(2, 4)$, $(3, 1)$, $(4, 2)$, $(5, 3)$. The corresponding meals have charms: $4$, $2$, $2$, $2$, $2$. The resulting minimum charm is $2$.

In the third test case, one way to maximize the minimum charm is to pair up the three appetizers with spiciness $0$ with the three main dishes with spiciness $100$, and the three appetizers with spiciness $100$ with the three main dishes with spiciness $0$. Doing so, the charm of each meal will be exactly $100$.

题目大意：
这道题目是关于配对捷克菜肴中的开胃菜和主菜，使得每对菜肴的辣度差（即魅力值）尽可能大。给定的开胃菜和主菜各有n道，每道菜都有相应的辣度值。需要将这些菜配对，使得所有配对中的最小辣度差尽可能大。

输入数据格式：
- 第一行包含一个整数t（1≤t≤1000），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数n（1≤n≤5000），表示开胃菜和主菜的数量。
- 第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i≤10^9），表示n道开胃菜的辣度。
- 第三行包含n个整数b_1, b_2, ..., b_n（0≤b_i≤10^9），表示n道主菜的辣度。
- 所有测试用例中n^2的总和不超过25×10^6。

输出数据格式：
- 对于每个测试用例，输出能够达到的最大最小辣度差。

示例输入输出：
```
Input
4
3
0 0 0
1000000000 1000000000 1000000000
5
1 2 3 4 5
1 2 3 4 5
6
0 0 0 100 100 100
100 100 100 0 0 0
7
14 25 62 74 86 95 12
51 62 71 72 92 20 84

Output
1000000000
2
100
30
```

注意：
- 在第一个测试用例中，无论怎样配对，每道菜的辣度差都是1000000000。
- 在第二个测试用例中，一种最优的配对方式是：(1, 5), (2, 4), (3, 1), (4, 2), (5, 3)，对应的最小辣度差是2。
- 在第三个测试用例中，一种最大化最小辣度差的方式是将辣度为0的三道开胃菜与辣度为100的三道主菜配对，辣度为100的三道开胃菜与辣度为0的三道主菜配对，每道菜的辣度差都是100。题目大意： 这道题目是关于配对捷克菜肴中的开胃菜和主菜，使得每对菜肴的辣度差（即魅力值）尽可能大。给定的开胃菜和主菜各有n道，每道菜都有相应的辣度值。需要将这些菜配对，使得所有配对中的最小辣度差尽可能大。 输入数据格式： - 第一行包含一个整数t（1≤t≤1000），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数n（1≤n≤5000），表示开胃菜和主菜的数量。 - 第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i≤10^9），表示n道开胃菜的辣度。 - 第三行包含n个整数b_1, b_2, ..., b_n（0≤b_i≤10^9），表示n道主菜的辣度。 - 所有测试用例中n^2的总和不超过25×10^6。 输出数据格式： - 对于每个测试用例，输出能够达到的最大最小辣度差。 示例输入输出： ``` Input 4 3 0 0 0 1000000000 1000000000 1000000000 5 1 2 3 4 5 1 2 3 4 5 6 0 0 0 100 100 100 100 100 100 0 0 0 7 14 25 62 74 86 95 12 51 62 71 72 92 20 84 Output 1000000000 2 100 30 ``` 注意： - 在第一个测试用例中，无论怎样配对，每道菜的辣度差都是1000000000。 - 在第二个测试用例中，一种最优的配对方式是：(1, 5), (2, 4), (3, 1), (4, 2), (5, 3)，对应的最小辣度差是2。 - 在第三个测试用例中，一种最大化最小辣度差的方式是将辣度为0的三道开胃菜与辣度为100的三道主菜配对，辣度为100的三道开胃菜与辣度为0的三道主菜配对，每道菜的辣度差都是100。