Similar statements (6) P34848

Consider two infinite horizontal lines A and B, separated ℓ units apart. The line A has m ‍points at the abscissae a₁, …, a_m. The line B has n points at the abscissae b₁, …, b_n. Given p ‍different indices i₁, …, i_p choosen from {1 … m}, and p different indices j₁, …, j_p choosen from {1 … n}, define d_k as the Euclidean distance between a_ik and b_jk, that is,

You are given ℓ, p, and the points in A and in B. Pick i₁, …, i_p and j₁, …, 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 ℓ, p, m and n. Follow a₁ ≤ a₂ ≤ … ≤ a_m−1 ≤ a_m. Follow b₁ ≤ b₂ ≤ … ≤ b_n−1 ≤ b_n. Assume ℓ ≤ 10⁶, p ≤ min(m, n), and that the absolute value of each abscissa is at most 10⁶.

Additionally, assume that m and n are at most 10⁵.

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.