Dr. Q is observing the motion of particles in a circular container. Let us establish a Cartesian coordinate system where the center of the circular container is at $(x_0, y_0)$ and its radius is $R$. There are several particles in the container. Suppose the $i$-th particle is at position $(x_i, y_i)$ at time $t=0$ with velocity $(vx_i, vy_i)$ (note: this is a velocity vector; if no collision occurs, its position at time $t$ should be $(x_i + t \cdot vx_i, y_i + t \cdot vy_i)$). Assume that the motion of all particles is independent. If a particle hits the wall of the container at any time, it undergoes a perfectly elastic collision, meaning its velocity direction is reflected according to the tangent at the point of collision, and its speed remains unchanged (as shown in the figure). Collisions are considered to be instantaneous.

Although collisions do not affect the speed of the particles, the particles suffer some damage. If a particle hits the container wall $k$ times, it will perish upon the $k$-th collision.

For research purposes, Dr. Q wants to know the minimum distance between any two particles during the time interval from $t=0$ until all particles have perished. Can you help him?

Input

The first line contains three real numbers: $x_0, y_0, R$, representing the center coordinates and radius of the circular container. The second line contains two positive integers $N$ and $k$, representing the total number of particles and the number of collisions until death, respectively. The next $N$ lines each contain four real numbers: $x_i, y_i, vx_i, vy_i$. It is guaranteed that $(x_i, y_i)$ are inside the circle and $(vx_i, vy_i)$ are non-zero.

Output

The output contains only one real number, which is the minimum historical distance between any two particles, rounded to three decimal places.

Examples

Input 1

0 0 10
2 10
0 -5 0 1
5 0 1 0

Output 1

7.071

Constraints

For all data, $2 \le N \le 100$, $1 \le k \le 100$. Please pay attention to real number precision issues.