시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 64 MB 4 4 4 100.000%

문제

After spending most of his money on various projects, Nadan decided to afford high quality shoes for his software developers. Luckily for Nadan, he found N left shoes and M right shoes in his basement. Since their origin is unknown, the shoes come in various sizes.

Nadan asked you to pair as many shoes as possible (it’s important that a new pair cannot be selected after pairing all the shoes). Each pair should consist of one left shoe and one right shoe. While pairing the shoes, you should make sure that the ugliness is minimized. The ugliness of one pairing is defined as the maximal absolute difference of the shoe sizes between all pairs of shoes.

입력

The first line contains two positive integers N and M (1 ≤ N, M ≤ 100 000), the number of left shoes and right shoes, in that order.

The second line contains N numbers Li (1 ≤ Li ≤ 109), the sizes of the left shoes.

The third line contains M numbers Ri (1 ≤ Ri ≤ 109), the sizes of the right shoes.

출력

Output the minimal ugliness between all possible shoe pairings.

예제 입력 1

2 3
2 3
1 2 3

예제 출력 1

0

예제 입력 2

4 3
2 39 41 45
39 42 46

예제 출력 2

1

Nadan has 4 left and 3 right shoes, maximal number of pairs that can be obtained is 3. One possible pairing is: 39 - 46, 41 - 42, 45 - 39, but ugliness of such pairing is 7 because of the first pair.

Better pairing would be: 39 - 39, 41 - 42, 45 - 46, with ugliness being equal to 1, which is minimal possible ugliness that can be obtained.

예제 입력 3

5 5
7 6 1 2 10
9 11 6 3 12

예제 출력 3

4