Anda diberikan bilangan bulat $n, m, k$ dan sebuah barisan yang terdiri dari $n$ bilangan bulat $a_i \in [1, m]$. Anda dapat paling banyak satu kali memilih suatu interval dari barisan tersebut (sebuah subbarisan berurutan) dengan panjang $k$ lalu merata-ratakannya, yaitu mengganti elemen-elemen pada interval ini dengan rata-rata aritmetikanya. Proses ini memakan $1$ satuan waktu, dan setiap elemen pada interval tersebut berubah secara seragam dengan laju konstan. Sebagai contoh, interval dengan elemen-elemen $(3, 9, 5, 1)$ memiliki rata-rata $\frac{3+9+5+1}{4} = 4\frac{1}{2}$, sehingga setelah waktu $t = \frac{2}{3}$ nilai-nilainya menjadi $(4, 6, 4\frac{2}{3}, 3\frac{1}{3})$, dan setelah waktu $t = 1$ menjadi $(4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2}, 4\frac{1}{2})$. Secara formal, setelah waktu $t \in [0, 1]$, sebuah elemen dengan nilai awal $a$ bernilai $a' = \bar{a} \cdot t + a \cdot (1 - t)$, di mana $\bar{a}$ adalah rata-rata interval tersebut. Hanya elemen-elemen di dalam interval terpilih yang berubah.

Secara independen untuk setiap bilangan $x$ dari $1$ hingga $m$, tugas Anda adalah menentukan seberapa cepat nilai $x$ dapat muncul di mana saja di dalam barisan, dengan melakukan proses perataan pada suatu interval. Setelah berapa lama hal ini dapat terjadi? Cetak -1 jika tidak mungkin memperoleh bilangan $x$.

Masukan

Baris pertama berisi tiga bilangan bulat $n$, $m$, dan $k$ ($1 \le k \le n \le 300\,000$; $1 \le m \le 500\,000$), yang masing-masing menyatakan panjang barisan, batas atas nilai, dan panjang interval yang dimodifikasi.

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$).

Keluaran

Cetak $m$ baris. Pada baris ke-$x$, cetak waktu minimum yang diperlukan (sebuah bilangan riil) untuk memperoleh bilangan $x$, atau cetak bilangan bulat -1 (tanpa titik desimal) jika tidak mungkin menggunakan paling banyak satu operasi perataan.

Galat mutlak yang dapat diterima adalah $10^{-9}$. Anda boleh mencetak hingga $20$ angka di belakang koma.

Contoh

Masukan 1

8 10 4
3 9 5 1 1 1 1 10

Keluaran 1

0.0000000000
0.2857142857
0.0000000000
0.3333333333
0.0000000000
0.5925925926
0.4000000000
0.2000000000
0.0000000000
0.0000000000

Masukan 2

1 3 1
2

Keluaran 2

-1
0.0000000000
-1

Catatan

Pada uji pertama, kita dapat merata-ratakan satu interval dengan panjang $k = 4$. Hasil eksaknya adalah $0, \frac{2}{7}, 0, \frac{1}{3}, 0, \frac{16}{27}, \frac{2}{5}, \frac{1}{5}, 0, 0$.

Bilangan $x = 6$ dapat diperoleh paling cepat pada waktu $t = \frac{16}{27} \approx 0.5926$, dengan merata-ratakan empat bilangan terakhir $(1, 1, 1, 10)$ menuju rata-rata $\frac{13}{4} = 3\frac{1}{4}$. Elemen terakhir kemudian bernilai $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.

Bilangan $x = 7$ dapat diperoleh paling cepat pada waktu $t = \frac{2}{5}$, dengan merata-ratakan interval $(9, 5, 1, 1)$ menuju rata-rata $4$. Elemen pertama dari elemen-elemen ini kemudian bernilai $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.

Pada uji kedua, merata-ratakan satu elemen tunggal tidak mengubah nilainya. Hasil untuk $x = 2$ adalah $t = 0$, sedangkan bilangan $1$ dan $3$ tidak dapat dicapai.