#P17978. Linear Averaging

Linear Averaging

Linear Averaging

题目描述

给定三个整数 n,m,kn,m,k,以及长度为 nn 的整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n,其中 1≤ai≤m1\le a_i\le m。

你可以至多选择一次操作:选取一个长度恰好为 kk 的连续子段,将其中所有元素逐渐变为这个子段的算术平均值 aˉ\bar a。这一过程持续 11 单位时间,各元素以恒定速度变化。具体地,原值为 aa 的元素在时刻 t∈[0,1]t\in[0,1] 的值为

a′=aˉ t+a(1−t).a'=\bar a\,t+a(1-t).

子段之外的元素不变。例如,(3,9,5,1)(3,9,5,1) 的平均值为 9/29/2,在时刻 t=2/3t=2/3,它变为 (4,6,14/3,10/3)(4,6,14/3,10/3)。

分别对每个整数 x=1,2,…,mx=1,2,\ldots,m,求至少一个序列元素变成 xx 所需的最短时间。如果原序列中已经有 xx,答案为 00;如果无论如何都不能得到 xx,答案为 −1-1。

每个 xx 的答案独立计算,可以选取不同的子段。

输入格式

第一行三个整数 n,m,kn,m,k。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出 mm 行。第 xx 行输出得到 xx 的最短时间;如果不可能,输出整数 -1。

非负答案允许的绝对误差为 10−910^{-9}。小数点后最多可以输出 2020 位数字。

数据范围

1≤k≤n≤3000001\le k\le n\le300000,1≤m≤5000001\le m\le500000,1≤ai≤m1\le a_i\le m。

样例 1

输入

8 10 4
3 9 5 1 1 1 1 10

输出

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

输出

-1
0.0000000000
-1

样例说明

第一组的精确答案为 0,2/7,0,1/3,0,16/27,2/5,1/5,0,00,2/7,0,1/3,0,16/27,2/5,1/5,0,0。

例如,选取最后四个数 (1,1,1,10)(1,1,1,10),它们的平均值为 13/413/4。最后一个元素在时刻 16/2716/27 变成 66。

第二组中,对单个元素取平均不会改变它,因此只有 22 可以得到。