정수 $n, m, k$와 $n$개의 정수 $a_i \in [1, m]$으로 이루어진 수열이 주어집니다. 여러분은 최대 한 번 수열에서 길이가 $k$인 구간(연속 부분수열)을 선택하여 평균화할 수 있습니다. 즉, 해당 구간의 원소들을 그 원소들의 산술 평균으로 대체할 수 있습니다. 이 과정은 $1$단위 시간이 걸리며, 구간의 각 원소는 일정한 속도로 균일하게 변합니다. 예를 들어 원소가 $(3, 9, 5, 1)$인 구간의 평균은 $\frac{3+9+5+1}{4} = 4\frac{1}{2}$이므로, 시간 $t = \frac{2}{3}$ 후에는 값들이 $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$이 되고, 시간 $t = 1$ 후에는 $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$가 됩니다. 엄밀하게는, 시간 $t \in [0, 1]$ 후 초기값이 $a$인 원소는 $a' = \bar{a} \cdot t + a \cdot (1 - t)$가 되며, 여기서 $\bar{a}$는 구간의 평균입니다. 선택된 구간에 속한 원소들만 변합니다.

$1$부터 $m$까지의 각 수 $x$에 대해 독립적으로, 어떤 구간을 평균화하는 과정을 수행하여 값 $x$가 수열의 어느 위치에든 얼마나 빨리 나타날 수 있는지 구해야 합니다. 얼마의 시간이 지난 후에 이것이 가능할까요? 만약 수 $x$를 얻는 것이 불가능하다면 -1을 출력하세요.

입력

첫 번째 줄에는 수열의 길이, 값의 상한, 그리고 변경할 구간의 길이를 각각 나타내는 세 정수 $n$, $m$, $k$ ($1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$)가 주어집니다.

두 번째 줄에는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$)이 주어집니다.

출력

$m$개의 줄을 출력합니다. $x$번째 줄에는 수 $x$를 얻는 데 필요한 최소 시간(실수)을 출력하거나, 최대 한 번의 평균화 연산으로 얻는 것이 불가능하다면 정수 -1(소수점 없이)을 출력합니다.

허용되는 절대 오차는 $10^{-9}$입니다. 소수점 아래 최대 $20$자리까지 출력할 수 있습니다.

예제

입력 1

8 10 4
3 9 5 1 1 1 1 10

출력 1

0.0000000000
0.2857142857
0.0000000000
0.3333333333
0.0000000000
0.5925925926
0.4000000000
0.2000000000
0.0000000000
0.0000000000

입력 2

1 3 1
2

출력 2

-1
0.0000000000
-1

노트

첫 번째 테스트에서는 길이가 $k = 4$인 구간 하나를 평균화할 수 있습니다. 정확한 결과는 $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$입니다.

수 $x = 6$은 마지막 네 수 $(1, 1, 1, 10)$을 평균 $\frac{13}{4} = 3\frac{1}{4}$로 평균화함으로써 시간 $t = \frac{16}{27} \approx 0.5926$에 가장 빨리 얻을 수 있습니다. 이때 마지막 원소는 $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$이 됩니다.

수 $x = 7$은 구간 $(9, 5, 1, 1)$을 평균 $4$로 평균화함으로써 시간 $t = \frac{2}{5}$에 가장 빨리 얻을 수 있습니다. 이때 이 원소들 중 첫 번째 원소는 $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$이 됩니다.

두 번째 테스트에서는 원소 하나를 평균화해도 값이 변하지 않습니다. $x = 2$에 대한 결과는 $t = 0$인 반면, 수 $1$과 $3$은 도달할 수 없습니다.