You are given integers $n, m, k$ and a sequence consisting of $n$ integers $a_i \in [1, m]$. You can at most once choose an interval of the sequence (a contiguous subsequence) of length $k$ and average it, that is, replace the elements of this interval with their arithmetic mean. This process takes $1$ unit of time, and each element of the interval changes uniformly with a constant speed. For example, the interval with elements $(3, 9, 5, 1)$ has an average of $\frac{3+9+5+1}{4} = 4\frac{1}{2}$, so after time $t = \frac{2}{3}$ the values are $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$, and after time $t = 1$ they become $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$. Formally, after time $t \in [0, 1]$, an element with initial value $a$ equals $a' = \bar{a} \cdot t + a \cdot (1 - t)$, where $\bar{a}$ is the mean of the interval. Only the elements in the chosen interval change.
Independently for each number $x$ from $1$ to $m$, your task is to determine how quickly the value $x$ can appear anywhere in the sequence, by performing the process of averaging some interval. After how much time is this possible? Print -1 if it is not possible to obtain the number $x$.
Input
The first line contains three integers $n$, $m$, and $k$ ($1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$), denoting respectively the length of the sequence, the upper limit of values, and the length of the modified interval.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).
Output
Print $m$ lines. In the $x$-th line, print the minimum required time (a real number) needed to obtain the number $x$, or print the integer -1 (without a dot) if it is not possible using at most one averaging operation.
The acceptable absolute error is $10^{-9}$. You may print up to $20$ digits after the decimal point.
Examples
Input 1
8 10 4 3 9 5 1 1 1 1 10
Output 1
0.0000000000 0.2857142857 0.0000000000 0.3333333333 0.0000000000 0.5925925926 0.4000000000 0.2000000000 0.0000000000 0.0000000000
Input 2
1 3 1 2
Output 2
-1 0.0000000000 -1
Note
In the first test, we can average one interval of length $k = 4$. The exact results are $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.
The number $x = 6$ can be obtained the earliest at time $t = \frac{16}{27} \approx 0.5926$, by averaging the last four numbers $(1, 1, 1, 10)$ to the mean $\frac{13}{4} = 3\frac{1}{4}$. The last element is then equal to $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.
The number $x = 7$ can be obtained the earliest at time $t = \frac{2}{5}$, by averaging the interval $(9, 5, 1, 1)$ to the mean $4$. The first of these elements is then equal to $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.
In the second test, averaging a single element does not change its value. The result for $x = 2$ is $t = 0$, whereas the numbers $1$ and $3$ are not reachable.