Bạn được cho các số nguyên $n, m, k$ và một dãy gồm $n$ số nguyên $a_i \in [1, m]$. Bạn có thể chọn nhiều nhất một lần một đoạn của dãy (một dãy con liên tiếp) có độ dài $k$ và trung bình hóa nó, tức là thay thế các phần tử của đoạn này bằng trung bình cộng của chúng. Quá trình này mất $1$ đơn vị thời gian, và mỗi phần tử của đoạn thay đổi đều đặn với tốc độ không đổi. Ví dụ, đoạn gồm các phần tử $(3, 9, 5, 1)$ có trung bình cộng là $\frac{3+9+5+1}{4} = 4\frac{1}{2}$, vì vậy sau thời gian $t = \frac{2}{3}$ các giá trị là $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$, và sau thời gian $t = 1$ chúng trở thành $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$. Một cách hình thức, sau thời gian $t \in [0, 1]$, một phần tử có giá trị ban đầu $a$ sẽ bằng $a' = \bar{a} \cdot t + a \cdot (1 - t)$, trong đó $\bar{a}$ là trung bình cộng của đoạn. Chỉ các phần tử trong đoạn được chọn mới thay đổi.
Một cách độc lập đối với mỗi số $x$ từ $1$ đến $m$, nhiệm vụ của bạn là xác định xem giá trị $x$ có thể xuất hiện ở bất kỳ đâu trong dãy nhanh nhất là bao lâu bằng cách thực hiện quá trình trung bình hóa một đoạn nào đó. Sau bao nhiêu thời gian thì điều này khả thi? Hãy in ra -1 nếu không thể thu được số $x$.
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên $n$, $m$ và $k$ ($1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$), lần lượt biểu thị độ dài của dãy, giới hạn trên của các giá trị và độ dài của đoạn được biến đổi.
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).
Kết quả
In ra $m$ dòng. Ở dòng thứ $x$, in ra thời gian tối thiểu cần thiết (một số thực) để thu được số $x$, hoặc in ra số nguyên -1 (không có dấu chấm) nếu không thể thu được bằng nhiều nhất một phép trung bình hóa.
Sai số tuyệt đối cho phép là $10^{-9}$. Bạn có thể in tối đa $20$ chữ số sau dấu thập phân.
Ví dụ
Dữ liệu vào 1
8 10 4 3 9 5 1 1 1 1 10
Kết quả 1
0.0000000000 0.2857142857 0.0000000000 0.3333333333 0.0000000000 0.5925925926 0.4000000000 0.2000000000 0.0000000000 0.0000000000
Dữ liệu vào 2
1 3 1 2
Kết quả 2
-1 0.0000000000 -1
Giải thích
Ở ví dụ đầu tiên, chúng ta có thể trung bình hóa một đoạn có độ dài $k = 4$. Các kết quả chính xác lần lượt là $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.
Số $x = 6$ có thể thu được sớm nhất tại thời điểm $t = \frac{16}{27} \approx 0.5926$, bằng cách trung bình hóa bốn số cuối cùng $(1, 1, 1, 10)$ về giá trị trung bình $\frac{13}{4} = 3\frac{1}{4}$. Khi đó phần tử cuối cùng bằng $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.
Số $x = 7$ có thể thu được sớm nhất tại thời điểm $t = \frac{2}{5}$, bằng cách trung bình hóa đoạn $(9, 5, 1, 1)$ về giá trị trung bình $4$. Khi đó phần tử đầu tiên trong các phần tử này bằng $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.
Ở ví dụ thứ hai, việc trung bình hóa một phần tử duy nhất không làm thay đổi giá trị của nó. Kết quả cho $x = 2$ là $t = 0$, trong khi các số $1$ và $3$ không thể đạt tới.