Gefnar eru heiltölurnar $n, m, k$ og runa sem samanstendur af $n$ heiltölum $a_i \in [1, m]$. Þú getur í mesta lagi einu sinni valið bil í rununni (samfellda hlutrunu) af lengd $k$ og tekið meðaltal þess, þ.e. skipt út stökunum á þessu bili fyrir reikningslegt meðaltal þeirra. Þetta ferli tekur $1$ tímaeiningu og hvert stak á bilinu breytist jafnt á föstum hraða. Til dæmis hefur bilið með stökunum $(3, 9, 5, 1)$ meðaltalið $\frac{3+9+5+1}{4} = 4\frac{1}{2}$, þannig að eftir tímann $t = \frac{2}{3}$ eru gildin $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$, og eftir tímann $t = 1$ verða þau $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$. Formlega gildir að eftir tímann $t \in [0, 1]$ er stak með upphafsgildi $a$ jafnt $a' = \bar{a} \cdot t + a \cdot (1 - t)$, þar sem $\bar{a}$ er meðaltal bilsins. Aðeins stökin á valda bilinu breytast.

Óháð fyrir hverja tölu $x$ frá $1$ til $m$ er verkefni þitt að ákvarða hversu fljótt gildið $x$ getur birst hvar sem er í rununni með því að framkvæma meðaltalsferlið á einhverju bili. Eftir hversu mikinn tíma er þetta mögulegt? Prentaðu -1 ef ekki er hægt að fá töluna $x$.

Inntak

Fyrsta línan inniheldur þrjár heiltölur $n$, $m$ og $k$ ($1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$), sem tákna lengd rununnar, efri mörk gilda og lengd breytta bilsins, í sömu röð.

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).

Úttak

Prentaðu $m$ línur. Í $x$-tu línunni skaltu prenta lágmarkstímann (rauntölu) sem þarf til að fá töluna $x$, eða prenta heiltöluna -1 (án punkts) ef það er ekki mögulegt með í mesta lagi einni meðaltalsaðgerð.

Leyfileg algildisskekkja er $10^{-9}$. Þú mátt prenta allt að $20$ aukastafi.

Dæmi

Inntak 1

8 10 4
3 9 5 1 1 1 1 10

Úttak 1

0.0000000000
0.2857142857
0.0000000000
0.3333333333
0.0000000000
0.5925925926
0.4000000000
0.2000000000
0.0000000000
0.0000000000

Inntak 2

1 3 1
2

Úttak 2

-1
0.0000000000
-1

Athugasemd

Í fyrra prófunartilvikinu getum við tekið meðaltal á einu bili af lengd $k = 4$. Nákvæmar niðurstöður eru $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.

Töluna $x = 6$ er hægt að fá fyrst á tímanum $t = \frac{16}{27} \approx 0.5926$, með því að taka meðaltal síðustu fjögurra talnanna $(1, 1, 1, 10)$ í meðaltalið $\frac{13}{4} = 3\frac{1}{4}$. Síðasta stakið er þá jafnt $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.

Töluna $x = 7$ er hægt að fá fyrst á tímanum $t = \frac{2}{5}$, með því að taka meðaltal bilsins $(9, 5, 1, 1)$ í meðaltalið $4$. Fyrsta stakið af þessum stökum er þá jafnt $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.

Í seinna prófunartilvikinu breytir meðaltal á einu staki ekki gildi þess. Niðurstaðan fyrir $x = 2$ er $t = 0$, en ekki er hægt að ná tölunum $1$ og $3$.