Se te dan los enteros $n, m, k$ y una secuencia que consta de $n$ enteros $a_i \in [1, m]$. Puedes elegir como máximo una vez un intervalo de la secuencia (una subsecuencia contigua) de longitud $k$ y promediarlo, es decir, reemplazar los elementos de este intervalo por su media aritmética. Este proceso toma $1$ unidad de tiempo, y cada elemento del intervalo cambia uniformemente a una velocidad constante. Por ejemplo, el intervalo con elementos $(3, 9, 5, 1)$ tiene un promedio de $\frac{3+9+5+1}{4} = 4\frac{1}{2}$, por lo que después del tiempo $t = \frac{2}{3}$ los valores son $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$, y después del tiempo $t = 1$ se convierten en $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$. Formalmente, después del tiempo $t \in [0, 1]$, un elemento con valor inicial $a$ es igual a $a' = \bar{a} \cdot t + a \cdot (1 - t)$, donde $\bar{a}$ es la media del intervalo. Solo cambian los elementos del intervalo elegido.

De forma independiente para cada número $x$ desde $1$ hasta $m$, tu tarea es determinar qué tan rápido puede aparecer el valor $x$ en cualquier lugar de la secuencia al realizar el proceso de promediar algún intervalo. ¿Después de cuánto tiempo es esto posible? Imprime -1 si no es posible obtener el número $x$.

Entrada

La primera línea contiene tres enteros $n$, $m$ y $k$ ($1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$), que indican respectivamente la longitud de la secuencia, el límite superior de los valores y la longitud del intervalo modificado.

La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).

Salida

Imprime $m$ líneas. En la $x$-ésima línea, imprime el tiempo mínimo requerido (un número real) necesario para obtener el número $x$, o imprime el entero -1 (sin punto decimal) si no es posible utilizando como máximo una operación de promediado.

El error absoluto aceptable es $10^{-9}$. Puedes imprimir hasta $20$ dígitos después del punto decimal.

Ejemplos

Entrada 1

8 10 4
3 9 5 1 1 1 1 10

Salida 1

0.0000000000
0.2857142857
0.0000000000
0.3333333333
0.0000000000
0.5925925926
0.4000000000
0.2000000000
0.0000000000
0.0000000000

Entrada 2

1 3 1
2

Salida 2

-1
0.0000000000
-1

Nota

En la primera prueba, podemos promediar un intervalo de longitud $k = 4$. Los resultados exactos son $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.

El número $x = 6$ se puede obtener lo antes posible en el tiempo $t = \frac{16}{27} \approx 0.5926$, promediando los últimos cuatro números $(1, 1, 1, 10)$ hacia la media $\frac{13}{4} = 3\frac{1}{4}$. El último elemento es entonces igual a $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.

El número $x = 7$ se puede obtener lo antes posible en el tiempo $t = \frac{2}{5}$, promediando el intervalo $(9, 5, 1, 1)$ hacia la media $4$. El primero de estos elementos es entonces igual a $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.

En la segunda prueba, promediar un solo elemento no cambia su valor. El resultado para $x = 2$ es $t = 0$, mientras que los números $1$ y $3$ no son alcanzables.