Sinulle annetaan kokonaisluvut $n, m, k$ sekä jono, joka koostuu $n$ kokonaisluvusta $a_i \in [1, m]$. Voit enintään kerran valita jonosta pituuden $k$ välin (yhtenäisen alijonon) ja keskiarvoistaa sen, eli korvata tämän välin alkiot niiden aritmeettisella keskiarvolla. Tämä prosessi kestää $1$ aikayksikön, ja jokainen välin alkio muuttuu tasaisesti vakionopeudella. Esimerkiksi välin, jonka alkiot ovat $(3, 9, 5, 1)$, keskiarvo on $\frac{3+9+5+1}{4} = 4\frac{1}{2}$, joten ajan $t = \frac{2}{3}$ kuluttua arvot ovat $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$, ja ajan $t = 1$ kuluttua niistä tulee $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$. Muodollisesti ajan $t \in [0, 1]$ kuluttua alkio, jonka alkuarvo oli $a$, on suuruudeltaan $a' = \bar{a} \cdot t + a \cdot (1 - t)$, missä $\bar{a}$ on välin keskiarvo. Vain valitun välin alkiot muuttuvat.
Tehtäväsi on määrittää toisistaan riippumatta jokaiselle luvulle $x$ väliltä $1$–$m$, kuinka nopeasti arvo $x$ voi ilmestyä mihin tahansa kohtaan jonoa, kun jokin väli keskiarvoistetaan. Kuinka pitkän ajan kuluttua tämä on mahdollista? Tulosta -1, jos lukua $x$ ei ole mahdollista saada.
Syöte
Ensimmäisellä rivillä on kolme kokonaislukua $n$, $m$ ja $k$ ($1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$), jotka ilmaisevat jonon pituuden, arvojen ylärajan sekä muokattavan välin pituuden.
Toisella rivillä on $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).
Tuloste
Tulosta $m$ riviä. Tulosta $x$:nnelle riville pienin vaadittu aika (reaaliluku), joka tarvitaan luvun $x$ saamiseen, tai tulosta kokonaisluku -1 (ilman desimaalipistettä), jos se ei ole mahdollista enintään yhdellä keskiarvoistamisoperaatiolla.
Sallittu absoluuttinen virhe on $10^{-9}$. Voit tulostaa enintään $20$ desimaalia.
Esimerkit
Syöte 1
8 10 4 3 9 5 1 1 1 1 10
Tuloste 1
0.0000000000 0.2857142857 0.0000000000 0.3333333333 0.0000000000 0.5925925926 0.4000000000 0.2000000000 0.0000000000 0.0000000000
Syöte 2
1 3 1 2
Tuloste 2
-1 0.0000000000 -1
Huomautus
Ensimmäisessä testissä voimme keskiarvoistaa yhden välin, jonka pituus on $k = 4$. Tarkat tulokset ovat $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.
Luku $x = 6$ voidaan saada aikaisintaan ajanhetkellä $t = \frac{16}{27} \approx 0.5926$ keskiarvoistamalla neljä viimeistä lukua $(1, 1, 1, 10)$ keskiarvoon $\frac{13}{4} = 3\frac{1}{4}$. Viimeinen alkio on tällöin $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.
Luku $x = 7$ voidaan saada aikaisintaan ajanhetkellä $t = \frac{2}{5}$ keskiarvoistamalla väli $(9, 5, 1, 1)$ keskiarvoon $4$. Näistä alkioista ensimmäinen on tällöin $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.
Toisessa testissä yksittäisen alkion keskiarvoistaminen ei muuta sen arvoa. Tulos luvulle $x = 2$ on $t = 0$, kun taas lukuja $1$ ja $3$ ei ole mahdollista saavuttaa.