Range k-th Maximum Query

你在学数据结构的时候碰到了如下问题：

给一个序列 $a_1, a_2, \dots, a_n$，求所有长度为$l$的子区间第$k$大的数的和。对于某个$i(1\leq i\leq n-l+1)$，将$a_i, a_{i+1}, \dots, a_{i+l-1}$所有的元素从大到小排序之后，得到$b_1, b_2, \dots, b_l$，其中的$b_k$就是所求的子区间$[i,i+l-1]$中第$k$大的数。对于其中所有的$i (1\leq i\leq n-l+1)$求和，就是想要的值。

比如一个序列为$3,1,5,2,4,1$，$l=4,k=2$，那么每个长度为$l$的区间中第$k$大的依次为$3,4,4$。

现在给你一个序列$c_1, c_2, \dots, c_n$，你想将其元素重新排列，使得这个和尽量大或者尽量小。问最大或者最小的和是多少。

第一行一个正整数$T(1\leq T\leq 10^4)$表示数据组数。

对于每组数据，第一行三个整数$n, l, k(1\leq k\leq l\leq n\leq 10^5)$。接下来一行$n$个正整数$c_1, c_2, \dots, c_n(1\leq c_i\leq 10^9)$。

保证$\sum n\leq 10^6$。

对于每组数据，输出两个数，分别表示最大最小的和。

1
6 4 2
1 2 3 4 5 6

15 10

一个可行的方案为 3, 4, 6, 5, 2, 1 和 5, 3, 2, 1, 6, 4。

2020 年百度之星·程序设计大赛 - 复赛