Similar statements (5) P12471

Consider two infinite horizontal lines $A$ and $B$, separated $\ell$ units apart. The line $A$ has $m$ points at the abscissae $a_1, \dots, a_m$. The line $B$ has $n$ points at the abscissae $b_1, \dots, b_n$. Given $p$ different indices $i_1, \dots, i_p$ choosen from $\{1 \dots m\}$, and $p$ different indices $j_1, \dots, j_p$ choosen from $\{1 \dots n\}$, define $d_k$ as the Euclidean distance between $a_{i_k}$ and $b_{j_k}$, that is, $$d_k = \sqrt{(a_{i_k} - b_{j_k})^2 + \ell^2} \enspace .$$

You are given $\ell$, $p$, and the points in $A$ and in $B$. Pick $i_1, \dots, i_p$ and $j_1, \dots, j_p$ in order to

Input

Input consists of several cases, each one with only integer numbers. Every case begins with four strictly positive numbers $\ell$, $p$, $m$ and $n$. Follow $a_1 \le a_2 \le \dots \le a_{m-1} \le a_m$. Follow $b_1 \le b_2 \le \dots \le b_{n-1} \le b_n$. Assume $\ell \le 10^6$, $p \le \min(m, n)$, and that the absolute value of each abscissa is at most $10^6$.

Additionally, assume that $m$ and $n$ are at most $10^4$.

Output

For every case, print the result with four digits after the decimal point. If you use the long double type, the input cases have no precision issues.