整数 $n, m, k$ と、$n$ 個の整数 $a_i \in [1, m]$ からなる数列が与えられます。あなたは高々 1 回、数列の長さ $k$ の区間（連続部分列）を 1 つ選んでそれを平均化する、すなわちその区間の要素をそれらの算術平均で置き換えることができます。この過程には $1$ 単位時間がかかり、区間の各要素は一定の速度で一様に変化します。例えば、要素 $(3, 9, 5, 1)$ を持つ区間の平均は $\frac{3+9+5+1}{4} = 4\frac{1}{2}$ なので、時間 $t = \frac{2}{3}$ の後には値は $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$ となり、時間 $t = 1$ の後には $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$ となります。形式的には、時間 $t \in [0, 1]$ の後、初期値 $a$ の要素は $a' = \bar{a} \cdot t + a \cdot (1 - t)$ に等しくなります（ここで $\bar{a}$ はその区間の平均です）。選ばれた区間内の要素のみが変化します。

$1$ から $m$ までの各数 $x$ について独立に、ある区間を平均化する過程を行うことで、値 $x$ が数列のどこかにどれだけ早く現れ得るかを求めてください。どれだけの時間の後にこれが可能になるでしょうか？数 $x$ を得ることが不可能な場合は -1 を出力してください。

入力

1 行目には、数列の長さ、値の上限、および変更する区間の長さをそれぞれ表す 3 つの整数 $n$、$m$、$k$（$1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$）が与えられます。

2 行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le m$）が与えられます。

出力

$m$ 行出力してください。$x$ 行目には、数 $x$ を得るために必要な最小時間（実数）を出力するか、高々 1 回の平均化操作では得ることが不可能な場合は整数 -1（小数点なし）を出力してください。

許容される絶対誤差は $10^{-9}$ です。小数点の後に最大 $20$ 桁まで出力して構いません。

入出力例

入力 1

8 10 4
3 9 5 1 1 1 1 10

出力 1

0.0000000000
0.2857142857
0.0000000000
0.3333333333
0.0000000000
0.5925925926
0.4000000000
0.2000000000
0.0000000000
0.0000000000

入力 2

1 3 1
2

出力 2

-1
0.0000000000
-1

ノート

1 番目のテストでは、長さ $k = 4$ の区間を 1 つ平均化できます。正確な結果は $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$ です。

数 $x = 6$ は、最後の 4 つの数 $(1, 1, 1, 10)$ を平均 $\frac{13}{4} = 3\frac{1}{4}$ へと平均化することで、最も早くて時間 $t = \frac{16}{27} \approx 0.5926$ に得られます。このとき最後の要素は $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$ に等しくなります。

数 $x = 7$ は、区間 $(9, 5, 1, 1)$ を平均 $4$ へと平均化することで、最も早くて時間 $t = \frac{2}{5}$ に得られます。このときこれらの要素の最初のものは $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$ に等しくなります。

2 番目のテストでは、単一の要素を平均化してもその値は変化しません。$x = 2$ に対する結果は $t = 0$ ですが、数 $1$ と $3$ には到達できません。