Du får gitt heltallene $n, m, k$ og en følge bestående av $n$ heltall $a_i \in [1, m]$. Du kan høyst én gang velge et intervall i følgen (en sammenhengende delfølge) med lengde $k$ og ta gjennomsnittet av det, det vil si erstatte elementene i dette intervallet med deres aritmetiske gjennomsnitt. Denne prosessen tar $1$ tidsenhet, og hvert element i intervallet endrer seg jevnt med konstant hastighet. For eksempel har intervallet med elementene $(3, 9, 5, 1)$ et gjennomsnitt på $\frac{3+9+5+1}{4} = 4\frac{1}{2}$, så etter tiden $t = \frac{2}{3}$ er verdiene $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$, og etter tiden $t = 1$ blir de $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$. Formelt, etter tiden $t \in [0, 1]$, er et element med startverdi $a$ lik $a' = \bar{a} \cdot t + a \cdot (1 - t)$, der $\bar{a}$ er gjennomsnittet av intervallet. Bare elementene i det valgte intervallet endres.

Uavhengig for hvert tall $x$ fra $1$ til $m$ er oppgaven din å bestemme hvor raskt verdien $x$ kan dukke opp hvor som helst i følgen ved å utføre prosessen med å ta gjennomsnittet av et intervall. Etter hvor lang tid er dette mulig? Skriv ut -1 hvis det ikke er mulig å oppnå tallet $x$.

Inndata

Den første linjen inneholder tre heltall $n$, $m$ og $k$ ($1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$), som angir henholdsvis lengden på følgen, den øvre grensen for verdiene og lengden på det modifiserte intervallet.

Den andre linjen inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).

Utdata

Skriv ut $m$ linjer. På den $x$-te linjen skal du skrive ut den minimale tiden (et reelt tall) som trengs for å oppnå tallet $x$, eller skrive ut heltallet -1 (uten punktum) hvis det ikke er mulig ved bruk av høyst én gjennomsnittsoperasjon.

Den akseptable absolutte feilen er $10^{-9}$. Du kan skrive ut opptil $20$ sifre etter desimaltegnet.

Eksempler

Inndata 1

8 10 4
3 9 5 1 1 1 1 10

Utdata 1

0.0000000000
0.2857142857
0.0000000000
0.3333333333
0.0000000000
0.5925925926
0.4000000000
0.2000000000
0.0000000000
0.0000000000

Inndata 2

1 3 1
2

Utdata 2

-1
0.0000000000
-1

Forklaring

I den første testen kan vi ta gjennomsnittet av ett intervall med lengde $k = 4$. De nøyaktige resultatene er $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.

Tallet $x = 6$ kan oppnås tidligst ved tiden $t = \frac{16}{27} \approx 0.5926$, ved å ta gjennomsnittet av de fire siste tallene $(1, 1, 1, 10)$ til gjennomsnittet $\frac{13}{4} = 3\frac{1}{4}$. Det siste elementet er da lik $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.

Tallet $x = 7$ kan oppnås tidligst ved tiden $t = \frac{2}{5}$, ved å ta gjennomsnittet av intervallet $(9, 5, 1, 1)$ til gjennomsnittet $4$. Det første av disse elementene er da lik $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.

I den andre testen endrer ikke gjennomsnittet av et enkelt element verdien dets. Resultatet for $x = 2$ er $t = 0$, mens tallene $1$ og $3$ ikke kan nås.