¡Bienvenido al concurso regional de Taoyuan de 2022 ICPC(International Collegiate Programming Contest)!

ICPC es una competición de programación algorítmica para estudiantes universitarios. Está diseñada para mostrar su creatividad, trabajo en equipo y capacidad para escribir código, analizar y resolver problemas bajo presión.

Este año hay $N$ autores de problemas para el concurso regional de Taoyuan, numerados de $1$ a $N$.

Para mejorar la calidad de toda la competición, los autores celebraron varias reuniones durante la preparación.

La elección del lugar de reunión es muy importante, ya que hay que tener en cuenta dónde viven los autores.

Para mayor comodidad, el organizador dividió a los autores en $K$ grupos. Cada grupo está formado por autores con números consecutivos, y cada autor pertenece únicamente a un grupo.

Los autores de un mismo grupo tendrán el mismo lugar de reunión. El coste del grupo se define como la mayor distancia entre uno de sus miembros y el lugar de reunión.

Ahora conoces la ubicación de los $N$ autores (como puntos de un sistema cartesiano bidimensional) y $K$. ¿Puedes hallar la suma mínima de costes de estos $K$ grupos?

La distancia se refiere aquí a la distancia euclídea: para dos puntos $(x_1,y_1)$ y $(x_2,y_2)$, es $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.

Este problema puede resultarte algo difícil. Además, descubres inesperadamente una información, aunque no sabes si será útil. La residencia de cada autor satisface cierta fórmula. En otras palabras, los $N$ puntos se generan mediante las siguientes fórmulas:

$$X_i=(Y_{i-1}\times233811181+1)\bmod(2^{31}-1),\quad\forall i\ge2.$$

$$Y_i=(X_i\times233811181+1)\bmod(2^{31}-1),\quad\forall i\ge1.$$

Las historias anteriores son puramente ficticias y cualquier coincidencia es puramente casual.

Entrada

La primera línea contiene tres enteros $N,K,X_1$, que representan, respectivamente, el número de puntos, el número de intervalos y la semilla aleatoria.

Restricciones

• $1\le K\le N\le2000$.

• $1\le X_1\le8831$.

Salida

Imprime un número de coma flotante que represente el valor mínimo de la suma de los radios de los círculos mínimos que encierran los puntos de los $K$ segmentos.

Tu respuesta se considerará correcta si el error absoluto o relativo en ambas coordenadas no supera $10^{-6}$. Formalmente, sea $a$ tu respuesta y $b$ la del jurado. La respuesta será correcta si $\frac{|a-b|}{\max(1,|b|)}\le10^{-6}$.

Ejemplos

Entrada 1

100 23 213

Salida 1

1319350480.8007326126