Сізге $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$ сандарына қол жеткізу мүмкін емес.