Ti vengono dati gli interi $n, m, k$ e una sequenza composta da $n$ interi $a_i \in [1, m]$. Puoi scegliere al più una volta un intervallo della sequenza (una sottosequenza contigua) di lunghezza $k$ e farne la media, vale a dire sostituire gli elementi di questo intervallo con la loro media aritmetica. Questo processo richiede $1$ unità di tempo e ciascun elemento dell'intervallo cambia uniformemente a velocità costante. Ad esempio, l'intervallo con elementi $(3, 9, 5, 1)$ ha una media pari a $\frac{3+9+5+1}{4} = 4\frac{1}{2}$, quindi dopo il tempo $t = \frac{2}{3}$ i valori sono $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$, e dopo il tempo $t = 1$ diventano $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$. Formalmente, dopo il tempo $t \in [0, 1]$, un elemento con valore iniziale $a$ è uguale a $a' = \bar{a} \cdot t + a \cdot (1 - t)$, dove $\bar{a}$ è la media dell'intervallo. Cambiano solo gli elementi nell'intervallo scelto.

Indipendentemente per ciascun numero $x$ da $1$ a $m$, il tuo compito è determinare quanto rapidamente il valore $x$ possa apparire in un punto qualsiasi della sequenza, eseguendo il processo di media su un qualche intervallo. Dopo quanto tempo ciò è possibile? Stampa -1 se non è possibile ottenere il numero $x$.

Input

La prima riga contiene tre interi $n$, $m$ e $k$ ($1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$), che indicano rispettivamente la lunghezza della sequenza, il limite superiore dei valori e la lunghezza dell'intervallo modificato.

La seconda riga contiene $n$ interi $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).

Output

Stampa $m$ righe. Nella $x$-esima riga, stampa il tempo minimo richiesto (un numero reale) necessario per ottenere il numero $x$, oppure stampa l'intero -1 (senza punto decimale) se non è possibile utilizzando al più un'operazione di media.

L'errore assoluto accettabile è $10^{-9}$. Puoi stampare fino a $20$ cifre dopo il punto decimale.

Esempi

Input 1

8 10 4
3 9 5 1 1 1 1 10

Output 1

0.0000000000
0.2857142857
0.0000000000
0.3333333333
0.0000000000
0.5925925926
0.4000000000
0.2000000000
0.0000000000
0.0000000000

Input 2

1 3 1
2

Output 2

-1
0.0000000000
-1

Note

Nel primo test possiamo fare la media di un intervallo di lunghezza $k = 4$. I risultati esatti sono $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.

Il numero $x = 6$ può essere ottenuto al più presto al tempo $t = \frac{16}{27} \approx 0.5926$, facendo la media degli ultimi quattro numeri $(1, 1, 1, 10)$ con media $\frac{13}{4} = 3\frac{1}{4}$. L'ultimo elemento è quindi uguale a $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.

Il numero $x = 7$ può essere ottenuto al più presto al tempo $t = \frac{2}{5}$, facendo la media dell'intervallo $(9, 5, 1, 1)$ con media $4$. Il primo di questi elementi è quindi uguale a $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.

Nel secondo test, fare la media di un singolo elemento non ne cambia il valore. Il risultato per $x = 2$ è $t = 0$, mentre i numeri $1$ e $3$ non sono raggiungibili.