Вам даны целые числа $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$ недостижимы.