Du får heltalen $n, m, k$ och en talföljd bestående av $n$ heltal $a_i \in [1, m]$. Du kan högst en gång välja ett intervall i talföljden (en sammanhängande delföljd) av längd $k$ och medelvärdesbilda det, det vill säga ersätta elementen i detta intervall med deras aritmetiska medelvärde. Denna process tar $1$ tidsenhet, och varje element i intervallet ändras likformigt med konstant hastighet. Till exempel har intervallet med elementen $(3, 9, 5, 1)$ medelvärdet $\frac{3+9+5+1}{4} = 4\frac{1}{2}$, så efter tiden $t = \frac{2}{3}$ är värdena $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$, och efter tiden $t = 1$ blir de $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$. Formellt gäller att efter tiden $t \in [0, 1]$ är ett element med startvärde $a$ lika med $a' = \bar{a} \cdot t + a \cdot (1 - t)$, där $\bar{a}$ är intervallets medelvärde. Endast elementen i det valda intervallet ändras.

Oberoende för varje tal $x$ från $1$ till $m$ är din uppgift att bestämma hur snabbt värdet $x$ kan dyka upp var som helst i talföljden genom att utföra medelvärdesbildning på något intervall. Efter hur lång tid är detta möjligt? Skriv ut -1 om det inte är möjligt att erhålla talet $x$.

Indata

Den första raden innehåller tre heltal $n$, $m$ och $k$ ($1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$), som anger längden på talföljden, den övre gränsen för värdena respektive längden på det modifierade intervallet.

Den andra raden innehåller $n$ heltal $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).

Utdata

Skriv ut $m$ rader. På den $x$-te raden, skriv ut den minsta nödvändiga tiden (ett reellt tal) som krävs för att erhålla talet $x$, eller skriv ut heltalet -1 (utan punkt) om det inte är möjligt med högst en medelvärdesoperation.

Det acceptabla absoluta felet är $10^{-9}$. Du får skriva ut upp till $20$ decimaler.

Exempel

Indata 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

Indata 2

1 3 1
2

Utdata 2

-1
0.0000000000
-1

Förklaring

I det första testet kan vi medelvärdesbilda ett intervall av längd $k = 4$. De exakta resultaten är $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.

Talet $x = 6$ kan erhållas tidigast vid tiden $t = \frac{16}{27} \approx 0.5926$, genom att medelvärdesbilda de fyra sista talen $(1, 1, 1, 10)$ mot medelvärdet $\frac{13}{4} = 3\frac{1}{4}$. Det sista elementet är då lika med $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.

Talet $x = 7$ kan erhållas tidigast vid tiden $t = \frac{2}{5}$, genom att medelvärdesbilda intervallet $(9, 5, 1, 1)$ mot medelvärdet $4$. Det första av dessa element är då lika med $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.

I det andra testet ändrar medelvärdesbildning av ett enskilt element inte dess värde. Resultatet för $x = 2$ är $t = 0$, medan talen $1$ och $3$ inte kan nås.