給定整數 $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$ 是無法達到的。