On vous donne des entiers $n, m, k$ et une suite composée de $n$ entiers $a_i \in [1, m]$. Vous pouvez au plus une fois choisir un intervalle de la suite (une sous-suite contiguë) de longueur $k$ et en faire la moyenne, c'est-à-dire remplacer les éléments de cet intervalle par leur moyenne arithmétique. Ce processus prend $1$ unité de temps, et chaque élément de l'intervalle évolue uniformément à vitesse constante. Par exemple, l'intervalle ayant pour éléments $(3, 9, 5, 1)$ a une moyenne de $\frac{3+9+5+1}{4} = 4\frac{1}{2}$, donc après le temps $t = \frac{2}{3}$ les valeurs sont $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$, et après le temps $t = 1$ elles deviennent $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$. Formellement, après un temps $t \in [0, 1]$, un élément de valeur initiale $a$ vaut $a' = \bar{a} \cdot t + a \cdot (1 - t)$, où $\bar{a}$ est la moyenne de l'intervalle. Seuls les éléments de l'intervalle choisi changent.
Indépendamment pour chaque nombre $x$ de $1$ à $m$, votre tâche consiste à déterminer à quelle vitesse la valeur $x$ peut apparaître n'importe où dans la suite en effectuant le processus de moyennage d'un certain intervalle. Au bout de combien de temps cela est-il possible ? Affichez -1 s'il n'est pas possible d'obtenir le nombre $x$.
Entrée
La première ligne contient trois entiers $n$, $m$ et $k$ ($1 \le k \le n \le 300\,000$ ; $1 \le m \le 500\,000$), désignant respectivement la longueur de la suite, la borne supérieure des valeurs et la longueur de l'intervalle modifié.
La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).
Sortie
Affichez $m$ lignes. Sur la $x$-ème ligne, affichez le temps minimum requis (un nombre réel) pour obtenir le nombre $x$, ou affichez l'entier -1 (sans point décimal) si cela est impossible en utilisant au plus une opération de moyennage.
L'erreur absolue acceptable est de $10^{-9}$. Vous pouvez afficher jusqu'à $20$ chiffres après la virgule.
Exemples
Entrée 1
8 10 4 3 9 5 1 1 1 1 10
Sortie 1
0.0000000000 0.2857142857 0.0000000000 0.3333333333 0.0000000000 0.5925925926 0.4000000000 0.2000000000 0.0000000000 0.0000000000
Entrée 2
1 3 1 2
Sortie 2
-1 0.0000000000 -1
Note
Dans le premier test, nous pouvons faire la moyenne d'un intervalle de longueur $k = 4$. Les résultats exacts sont $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.
Le nombre $x = 6$ peut être obtenu au plus tôt à l'instant $t = \frac{16}{27} \approx 0.5926$, en moyennant les quatre derniers nombres $(1, 1, 1, 10)$ vers la moyenne $\frac{13}{4} = 3\frac{1}{4}$. Le dernier élément vaut alors $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.
Le nombre $x = 7$ peut être obtenu au plus tôt à l'instant $t = \frac{2}{5}$, en moyennant l'intervalle $(9, 5, 1, 1)$ vers la moyenne $4$. Le premier de ces éléments vaut alors $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.
Dans le deuxième test, faire la moyenne d'un seul élément ne change pas sa valeur. Le résultat pour $x = 2$ est $t = 0$, tandis que les nombres $1$ et $3$ ne sont pas atteignables.