给你整数 $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 是无法达到的。