Optimal Chip Battery Allocation

You are manufacturing advanced chips for machines. Each machine contains two chips. To power a chip you must assign it k batteries out of a stockpile of 2n*k batteries. The power output of a chip is defined as the smallest power output among the k batteries allocated to it.

A machine works best when its two chips produce almost the same power. In other words, if one chip has power x and the other has power y, then the machine’s performance is best if the absolute difference |x-y| is as small as possible. Since you have n machines (hence, 2n chips), you are free to assign the batteries arbitrarily to the chips, provided that every chip gets exactly k batteries and every battery is used exactly once.

Your goal is to make an allocation so that, in every machine, the difference between the power outputs of its two chips is at most d – and you wish to achieve the smallest possible such d. It turns out that, in any feasible allocation, you must use the 2n smallest batteries as the chip‐minima in order to ensure that every chip’s fillers (the remaining batteries used in that chip) have higher power than the chip’s minimum. Therefore, if you sort all batteries in non‐decreasing order as \(a_0,a_1,\dots,a_{2nk-1}\), then an optimal allocation is obtained by choosing the first \(2n\) batteries to be the chip minimums. You are allowed to pair the \(2n\) chip minimums arbitrarily into \(n\) machines. It can be shown that the best pairing is to pair the two smallest chip minimums, the next two smallest, and so on. With this pairing the difference in a machine is \(a_{2i+1}-a_{2i}\) for \(i=0,1,\dots,n-1\) and the overall performance guarantee is given by

[ d = \max_{0 \le i < n} {a_{2i+1}-a_{2i}}. ]

Given n, k and the power outputs of the \(2nk\) batteries, determine the minimum possible d that can be guaranteed in an optimal allocation.

inputFormat

The first line of input contains two integers n and k (1 ≤ n, k ≤ 10⁵) representing the number of machines and the number of batteries per chip, respectively.

The second line contains 2*n*k space‐separated integers, each representing the power output of a battery. It is guaranteed that each battery power is an integer between 1 and 10⁹.

outputFormat

Output a single integer d – the smallest possible maximum difference between the two chips in any machine under an optimal battery allocation.

sample

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

1