Optimal Curling Center

Curling is a sport where players slide stones on a sheet of ice toward a target area. In this problem, two teams (Red and Blue) compete on the number line. After the game, there are \(n+m\) stones remaining: \(n\) stones for Red and \(m\) for Blue. The positions of the Red stones are given as \(a_1, a_2, \dots, a_n\) and those of the Blue stones as \(b_1, b_2, \dots, b_m\).

For a chosen real number \(c\) (the center of the target), a Red stone at position \(a\) is said to qualify if

\[ |c-a| < |c-b| \quad \text{for every Blue stone } b. \]

If exactly \(p\) Red stones satisfy this, then Red wins the game and scores \(p\) points. Your task is to choose \(c\) so that Red wins (i.e. there is at least one Red stone satisfying the condition) and the score \(p\) is maximized.

Note: \(c\) can be any real number and does not have to be an integer.

Hint: For each Red stone \(a\), one may show that the stone qualifies if and only if \(c\) lies in the open interval \[ \Big( L, R \Big) \quad \text{where } L = \max_{b a} \frac{a+b}{2} \; (\text{or } +\infty \text{ if none}). \] The answer then is to choose \(c\) that lies in the maximum number of these intervals.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq 10^5)\) representing the number of Red and Blue stones respectively.

The second line contains \(n\) space-separated real numbers \(a_1, a_2, \dots, a_n\) representing the positions of the Red stones.

The third line contains \(m\) space-separated real numbers \(b_1, b_2, \dots, b_m\) representing the positions of the Blue stones.

It is possible that the positions are given in any order.

outputFormat

Output a real number \(c\) representing the center of the target area such that the number of qualifying Red stones is maximized. If there are multiple valid answers, output any. The output should have an absolute or relative error of at most \(10^{-6}\).

sample

2 2
0 10
5 20

1.5