Problem Description

Alice and Bob are playing a game. Alice has a sequence of $n$ integers $a$, and Bob has a sequence of $n$ integers $b$. In each round, a player removes one number from their sequence. The players take turns, with Alice starting first.

When both sequences have only one number left, the game ends. Let the remaining number in Alice's sequence be $x$ and the remaining number in Bob's sequence be $y$. Alice wants to maximize the absolute difference between $x$ and $y$, while Bob wants to minimize this value. Both players play optimally.

Calculate the result of the game when both players play optimally.

Input Format

The first line contains an integer $n \ (1 \leq n \leq 1,000)$, representing the number of integers in each sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n \ (1 \leq a_i \leq 10^9)$, representing the integers in Alice's sequence.

The third line contains $n$ integers $b_1, b_2, \dots, b_n \ (1 \leq b_i \leq 10^9)$, representing the integers in Bob's sequence.

Output Format

Output the absolute difference between $x$ and $y$ when both players play optimally.

Sample Input and Output

Sample Input #1

4
2 14 7 14
5 10 9 22

Sample Output #1

4

Sample Input #2

1
14
42

Sample Output #2

28

Notes

In the first sample, $x=14$ and $y=10$, so the absolute difference is $4$.

In the second sample, both sequences have only one number left, so $x=14$ and $y=42$.

见题面 Input 部分

见题面 Output 部分