Gegeben sind ganze Zahlen $n, m, k$ und eine Folge aus $n$ ganzen Zahlen $a_i \in [1, m]$. Sie können höchstens einmal ein Intervall der Folge (eine zusammenhängende Teilfolge) der Länge $k$ auswählen und mitteln, d. h. die Elemente dieses Intervalls durch ihr arithmetisches Mittel ersetzen. Dieser Vorgang dauert $1$ Zeiteinheit, und jedes Element des Intervalls ändert sich gleichmäßig mit konstanter Geschwindigkeit. Beispielsweise hat das Intervall mit den Elementen $(3, 9, 5, 1)$ einen Mittelwert von $\frac{3+9+5+1}{4} = 4\frac{1}{2}$, sodass die Werte nach der Zeit $t = \frac{2}{3}$ gleich $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$ sind und nach der Zeit $t = 1$ zu $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$ werden. Formal gilt nach der Zeit $t \in [0, 1]$ für ein Element mit Anfangswert $a$ der Wert $a' = \bar{a} \cdot t + a \cdot (1 - t)$, wobei $\bar{a}$ der Mittelwert des Intervalls ist. Nur die Elemente im gewählten Intervall ändern sich.

Unabhängig für jede Zahl $x$ von $1$ bis $m$ besteht Ihre Aufgabe darin zu bestimmen, wie schnell der Wert $x$ durch das Mitteln eines Intervalls irgendwo in der Folge auftreten kann. Nach wie viel Zeit ist dies möglich? Geben Sie -1 aus, wenn es nicht möglich ist, die Zahl $x$ zu erhalten.

Eingabe

Die erste Zeile enthält drei ganze Zahlen $n$, $m$ und $k$ ($1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$), die jeweils die Länge der Folge, die Obergrenze der Werte und die Länge des modifizierten Intervalls angeben.

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).

Ausgabe

Geben Sie $m$ Zeilen aus. Geben Sie in der $x$-ten Zeile die minimal erforderliche Zeit (eine reelle Zahl) aus, die benötigt wird, um die Zahl $x$ zu erhalten, oder geben Sie die ganze Zahl -1 (ohne Dezimalpunkt) aus, wenn dies mit höchstens einer Mittelungsoperation nicht möglich ist.

Der zulässige absolute Fehler beträgt $10^{-9}$. Sie dürfen bis zu $20$ Nachkommastellen ausgeben.

Beispiele

Eingabe 1

8 10 4
3 9 5 1 1 1 1 10

Ausgabe 1

0.0000000000
0.2857142857
0.0000000000
0.3333333333
0.0000000000
0.5925925926
0.4000000000
0.2000000000
0.0000000000
0.0000000000

Eingabe 2

1 3 1
2

Ausgabe 2

-1
0.0000000000
-1

Hinweis

Im ersten Test können wir ein Intervall der Länge $k = 4$ mitteln. Die exakten Ergebnisse lauten $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.

Die Zahl $x = 6$ kann frühestens zum Zeitpunkt $t = \frac{16}{27} \approx 0.5926$ erreicht werden, indem die letzten vier Zahlen $(1, 1, 1, 10)$ auf den Mittelwert $\frac{13}{4} = 3\frac{1}{4}$ gemittelt werden. Das letzte Element ist dann gleich $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.

Die Zahl $x = 7$ kann frühestens zum Zeitpunkt $t = \frac{2}{5}$ erreicht werden, indem das Intervall $(9, 5, 1, 1)$ auf den Mittelwert $4$ gemittelt wird. Das erste dieser Elemente ist dann gleich $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.

Im zweiten Test ändert das Mitteln eines einzelnen Elements dessen Wert nicht. Das Ergebnis für $x = 2$ ist $t = 0$, während die Zahlen $1$ und $3$ nicht erreichbar sind.