Problem Description

At ACoder, we are planning to hold a programming contest with two teams, Team Takahashi and Team Aoki, competing against each other. There are $N$ candidates for Team Takahashi, and the strength of the $i$-th candidate for Team Takahashi is represented by $A_i$. There are also $M$ candidates for Team Aoki, and the strength of the $i$-th candidate for Team Aoki is represented by $B_i$.

Before the contest, we decided to select $K$ participants from each team from their respective candidates. Here, we define the strength difference between the teams as follows:

• Let $X_i$ be the strength of the $i$-th strongest participant in Team Takahashi, and $Y_i$ be the strength of the $i$-th strongest participant in Team Aoki.
• The strength difference between the teams is then $max\ (|X_1\ -\ Y_1|,\ |X_2\ -\ Y_2|,\ ...,\ |X_K\ -\ Y_K|\ )$.

Find the minimum strength difference between the teams when the participants are decided.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $ $ B_1 $ $ B_2 $ $ ... $ $ B_M $

Output Format

Output the minimum strength difference between the teams.

Sample Input and Output

Sample Input #1

3 4 2
2 11 16
4 7 9 10

Sample Output #1

2

Sample Input #2

6 5 3
15 7 14 3 14 11
20 18 15 18 17

Sample Output #2

3

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ M\ \leq\ 10^5$
• $1\ \leq\ K\ \leq\ min\ (N,\ M)$
• $1\ \leq\ A_i\ \leq\ 10^9$
• $1\ \leq\ B_i\ \leq\ 10^9$
• $A_i,\ B_i$ are integers

Sample Explanation 1

It is best to select the $1$-st and $2$-nd candidates from Team Takahashi and the $1$-st and $3$-rd candidates from Team Aoki as participants. In this case, the strengths of Team Takahashi's participants are $11$ and $2$ in descending order, and the strengths of Team Aoki's participants are $9$ and $4$ in descending order.

见题面 Input 部分

见题面 Output 部分