Dane są liczby całkowite $n, m, k$ oraz ciąg składający się z $n$ liczb całkowitych $a_i \in [1, m]$. Możesz co najwyżej raz wybrać przedział ciągu (spójny podciąg) o długości $k$ i go uśrednić, to znaczy zastąpić elementy tego przedziału ich średnią arytmetyczną. Proces ten trwa $1$ jednostkę czasu, a każdy element przedziału zmienia się jednostajnie ze stałą prędkością. Na przykład przedział o elementach $(3, 9, 5, 1)$ ma średnią równą $\frac{3+9+5+1}{4} = 4\frac{1}{2}$, więc po czasie $t = \frac{2}{3}$ wartości wynoszą $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$, a po czasie $t = 1$ stają się równe $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$. Formalnie, po czasie $t \in [0, 1]$ element o wartości początkowej $a$ jest równy $a' = \bar{a} \cdot t + a \cdot (1 - t)$, gdzie $\bar{a}$ jest średnią przedziału. Zmieniają się tylko elementy w wybranym przedziale.

Niezależnie dla każdej liczby $x$ od $1$ do $m$, Twoim zadaniem jest określenie, jak szybko wartość $x$ może pojawić się gdziekolwiek w ciągu w wyniku przeprowadzenia procesu uśredniania pewnego przedziału. Po jakim czasie jest to możliwe? Wypisz -1, jeśli otrzymanie liczby $x$ nie jest możliwe.

Wejście

Pierwszy wiersz zawiera trzy liczby całkowite $n$, $m$ oraz $k$ ($1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$), oznaczające odpowiednio długość ciągu, górne ograniczenie wartości oraz długość modyfikowanego przedziału.

Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).

Wyjście

Wypisz $m$ wierszy. W $x$-tym wierszu wypisz minimalny wymagany czas (liczbę rzeczywistą) potrzebny do uzyskania liczby $x$ lub wypisz liczbę całkowitą -1 (bez kropki), jeśli nie jest to możliwe przy użyciu co najwyżej jednej operacji uśredniania.

Dopuszczalny błąd bezwzględny wynosi $10^{-9}$. Możesz wypisać do $20$ cyfr po kropce dziesiętnej.

Przykłady

Wejście 1

8 10 4
3 9 5 1 1 1 1 10

Wyjście 1

0.0000000000
0.2857142857
0.0000000000
0.3333333333
0.0000000000
0.5925925926
0.4000000000
0.2000000000
0.0000000000
0.0000000000

Wejście 2

1 3 1
2

Wyjście 2

-1
0.0000000000
-1

Uwaga

W pierwszym teście możemy uśrednić jeden przedział o długości $k = 4$. Dokładne wyniki to $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.

Liczbę $x = 6$ można uzyskać najwcześniej w chwili $t = \frac{16}{27} \approx 0.5926$, uśredniając cztery ostatnie liczby $(1, 1, 1, 10)$ do średniej $\frac{13}{4} = 3\frac{1}{4}$. Ostatni element jest wtedy równy $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.

Liczbę $x = 7$ można uzyskać najwcześniej w chwili $t = \frac{2}{5}$, uśredniając przedział $(9, 5, 1, 1)$ do średniej $4$. Pierwszy z tych elementów jest wtedy równy $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.

W drugim teście uśrednienie pojedynczego elementu nie zmienia jego wartości. Wynik dla $x = 2$ to $t = 0$, natomiast liczby $1$ i $3$ są nieosiągalne.