2022 ICPC(International Collegiate Programming Contest) Taoyuan 지역 대회에 오신 것을 환영합니다!
ICPC는 대학생을 위한 알고리즘 프로그래밍 대회입니다. 대학생의 창의력, 팀워크, 그리고 압박 속에서 코드를 작성하고 분석하며 문제를 해결하는 능력을 보여 주도록 설계되었습니다.
올해 Taoyuan 지역 대회에는 $N$명의 출제자가 있으며 번호는 $1$부터 $N$까지입니다.
대회 전체의 질을 높이기 위해 출제자들은 준비 과정에서 여러 차례 회의를 열었습니다.
회의 장소를 선택하는 일은 매우 중요합니다. 출제자들의 거주지를 고려해야 하기 때문입니다.
편의를 위해 주최자는 출제자들을 $K$개 그룹으로 나누었습니다. 각 그룹은 번호가 연속인 출제자들로 구성되며, 각 출제자는 하나의 그룹에만 속합니다.
같은 그룹의 출제자들은 같은 회의 장소를 사용하며, 그룹의 비용은 그룹 구성원과 회의 장소 사이 거리의 최댓값으로 정의됩니다.
이제 $N$명의 출제자 위치(2차원 데카르트 좌표계의 점)와 $K$를 알고 있습니다. 이 $K$개 그룹의 비용 합의 최솟값을 구할 수 있나요?
여기서 거리는 유클리드 거리입니다. 즉, 두 점 $(x_1,y_1)$, $(x_2,y_2)$ 사이의 거리는 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$입니다.
이 문제는 조금 어려울 수 있습니다. 게다가 여러분은 뜻밖의 정보를 발견했지만, 유용한지는 모릅니다. 각 출제자의 거주지가 특정 공식을 만족한다는 것입니다. 즉, $N$개의 점은 다음 공식으로 생성됩니다.
$$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.$$
위 이야기는 모두 허구이며, 일치하는 점이 있다면 순전히 우연입니다.
입력
첫 줄에는 점의 개수, 구간의 개수, 난수 시드를 각각 나타내는 세 정수 $N,K,X_1$이 주어집니다.
제한
$1\le K\le N\le2000$.
$1\le X_1\le8831$.
출력
$K$개 구간의 최소 포함 원 반지름 합의 최솟값을 나타내는 부동소수점 수 하나를 출력하세요.
두 좌표 모두에서 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정됩니다. 엄밀히 말해 여러분의 답을 $a$, 심사위원의 답을 $b$라고 할 때, $\frac{|a-b|}{\max(1,|b|)}\le10^{-6}$이면 정답으로 인정됩니다.
예제
입력 1
100 23 213
출력 1
1319350480.8007326126