题意描述

给定一个长度为 $n$ 的正整数序列 $a$ 和一个固定的常数 $p$，定义 $f(l,r,p)$ 为 $[l,r]$ 所有长度大于 $1$ 的子区间的平均值的前 $p$ 大值中的某一个（取决于你自己的选择），$g(l,r,p)$ 为 $[l,r]$ 所有长度为大于 $1$ 的子区间的平均值的前 $p$ 小值中的某一个（同上）。

特别的，当区间长度小于 $2$ 时，$f,g$ 的值都为 $0$，且如果子区间个数小于 $p$，则任意选一个即可。

有 $q$ 次询问，每次给定 $k_1,k_2$，从数列中选出至多 $k_1+k_2$ 个不交的区间，其中 $k_1$ 个权值取其 $f$ 值，另外 $k_2$ 个权值取其 $g$ 值。

求所有合法策略下所能得到权值和的最大值。

输入格式

第一行三个整数 $n,q,p\ (1\le n\le 10^5,1\le q\le 5\times 10^5,3\le p \le n^2)$。

第二行 $n$ 个正整数 $a_i\ (1\le a_i\le 10^9)$。

第 $3$ 至 $q+2$ 行，每行两个正整数 $k_1,k_2\ (1\le k_1,k_2\le n)$。

输出格式

$q$ 行每行一个浮点数表示最大的权值。(必须四舍五入输出三位小数~~，绝不是因为没有 $spj$~~)。

样例

样例输入 #1

5 1 3
2 5 6 8 4
1 1

样例输出 #1

11.500

样例输入 #2

20 15 390
1 1 24 30 27 6 5 13 15 12 2 20 18 28 17 25 24 4 27 16 
2 2
1 1
1 1
2 2
3 2
2 1
5 1
7 1
2 1
2 2
1 1
1 4
1 1
2 1
2 1

样例输出 #2

97.500
53.000
53.000
97.500
116.000
76.000
131.000
153.500
76.000
97.500
53.000
116.000
53.000
76.000
76.000

样例解释

对于第一个样例，可以选择 $f(2,3,p)=5.5,\ g(4,5,p)=6$，总和为 $11.5$。

可以证明，没有比这种策略更优秀的选法。

说明 / 提示

对于 $10\%$ 的数据，$n\le 20$。

对于 $25\%$ 的数据，$n\le 100$。    

对于 $30\%$ 的数据，$n\le 500,p=n^2$。

对于另外 $10 \%$ 的数据，$k_1,k_2 \le 200$。

对于另外 $20 \%$ 的数据，$q=1$。

对于 $100\%$ 的数据，$1\le n\le 10^5,3\le p \le n^2,1\le q\le 5\times 10^5,1\le k_1,k_2\le n,1\le a_i\le 10^9$。

请注意 $p$ 的数据范围是 $3 \le p \le n^2$。