Вам задано цілі числа $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}$ — середнє арифметичне елементів відрізка. Змінюються лише елементи вибраного відрізка.

Незалежно для кожного числа $x$ від $1$ до $m$ ваше завдання — визначити, наскільки швидко значення $x$ може з'явитися будь-де в послідовності під час виконання процесу усереднення деякого відрізка. Через який час це можливо? Виведіть -1, якщо отримати число $x$ неможливо.

Вхідні дані

Перший рядок містить три цілі числа $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$ можна отримати найраніше в момент часу $t = \frac{16}{27} \approx 0.5926$, усереднюючи останні чотири числа $(1, 1, 1, 10)$ до середнього $\frac{13}{4} = 3\frac{1}{4}$. Тоді останній елемент дорівнюватиме $3\frac{1}{4} \cdot \frac{16}{27} + 10 \cdot \frac{11}{27} = 6$.

Число $x = 7$ можна отримати найраніше в момент часу $t = \frac{2}{5}$, усереднюючи відрізок $(9, 5, 1, 1)$ до середнього $4$. Тоді перший із цих елементів дорівнюватиме $4 \cdot \frac{2}{5} + 9 \cdot \frac{3}{5} = 7$.

У другому тесті усереднення одного елемента не змінює його значення. Результат для $x = 2$ дорівнює $t = 0$, тоді як числа $1$ і $3$ недосяжні.