畀定整數 $n, m, k$ 同埋一個由 $n$ 個整數 $a_i \in [1, m]$ 組成嘅序列。你最多可以揀一次序列入面一個長度為 $k$ 嘅區間（連續子序列）並將佢均值化，即係將呢個區間入面嘅元素替換成佢哋嘅算術平均數。呢個過程需要花費 $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。

輸入

第一行包含三個整數 $n$、$m$ 同 $k$（$1 \le k \le n \le 300\,000$；$1 \le m \le 500\,000$），分別代表序列嘅長度、數值嘅上限同埋被修改區間嘅長度。

第二行包含 $n$ 個整數 $a_1, a_2, \dots, a_n$（$1 \le a_i \le m$）。

輸出

輸出 $m$ 行。喺第 $x$ 行入面，輸出得到數字 $x$ 所需嘅最短時間（一個實數）；如果最多執行一次均值化操作都冇可能得到該數字，則輸出整數 -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

提示

喺第一個測試入面，我哋可以對一個長度為 $k = 4$ 嘅區間進行均值化。精確嘅結果分別係 $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$。

數字 $x = 6$ 最早可以喺時間 $t = \frac{16}{27} \approx 0.5926$ 嗰陣得到，方法係將最後四個數 $(1, 1, 1, 10)$ 均值化去平均數 $\frac{13}{4} = 3\frac{1}{4}$。呢個時候最後一個元素嘅值等於 $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$。

數字 $x = 7$ 最早可以喺時間 $t = \frac{2}{5}$ 嗰陣得到，方法係將區間 $(9, 5, 1, 1)$ 均值化去平均數 $4$。呢個時候呢啲元素入面嘅第一個就等於 $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$。

喺第二個測試入面，對單一元素進行均值化唔會改變佢嘅值。對於 $x = 2$，結果係 $t = 0$，而數字 $1$ 同 $3$ 係無法達到嘅。