Consider two infinite horizontal lines *A* and *B*,
separated ℓ units apart.
The line *A* has *m* points at the abscissae *a*_{1}, …, *a*_{m}.
The line *B* has *n* points at the abscissae *b*_{1}, …, *b*_{n}.
Given *p* different indices *i*_{1}, …, *i*_{p} choosen from {1 … *m*},
and *p* different indices *j*_{1}, …, *j*_{p} choosen from {1 … *n*},
define *d*_{k} as the Euclidean distance between *a*_{ik} and *b*_{jk},
that is,

d_{k} = | √ |
| . |

You are given ℓ, *p*, and the points in *A* and in *B*.
Peek *i*_{1}, …, *i*_{p} and *j*_{1}, …, *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*_{1} ≤ *a*_{2} ≤ … ≤ *a*_{m−1} ≤ *a*_{m}.
Follow *b*_{1} ≤ *b*_{2} ≤ … ≤ *b*_{n−1} ≤ *b*_{n}.
Assume ℓ ≤ 10^{6},
*p* ≤ 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**^{5}**.
**

**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.

Public test cases

**Input**

1 1 2 2 5 10 9 20 1 2 2 2 5 10 9 20 1000000 4 5 4 300000 300000 300000 300000 300000 -500000 -500000 -500000 -500000 3 2 7 4 0 2 4 6 8 10 12 1 4 7 10

**Output**

1.4142 1.4142 1280624.8475 3.0000

Information

- Author
- Salvador Roura
- Language
- English
- Other languages
- Spanish
- Official solutions
- C++
- User solutions
- C++
- Event
- Catorzè Concurs de Programació de la UPC - Semifinal
- Date
- 2016-06-29