2022 ICPC(International Collegiate Programming Contest) Taoyuan 地区大会へようこそ！
ICPCは大学生のためのアルゴリズムプログラミング競技です。大学生の創造力、チームワーク、そしてプレッシャーの中でコードを書き、分析し、問題を解く能力を披露するために設けられています。
今年の Taoyuan 地区大会には $N$ 人の出題者がおり、$1$から $N$ までの番号が付いています。
大会全体の質を高めるため、出題者たちは準備中に何度か会議を開きました。
会議場所の選び方はとても重要です。出題者の住む場所を考慮する必要があるからです。
便宜のため、主催者は出題者を $K$ 個のグループに分けました。各グループは連続する番号の出題者で構成され、各出題者は一つのグループにだけ属します。
同じグループの出題者は同じ会議場所を使い、そのグループのコストは、メンバーから会議場所までの距離の最大値と定義されます。
今、$N$人の出題者の位置（2次元デカルト座標上の点）と $K$ がわかっています。これら $K$ 個のグループのコストの和の最小値を求められますか？
ここでの距離はユークリッド距離です。つまり、2点 $(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.$$
以上の話はすべて架空のものであり、一致があったとしても純粋な偶然です。
入力
最初の行には、点の個数、区間の個数、乱数の種をそれぞれ表す3整数 $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