せやな~

题目背景

![](https://cdn.luogu.com.cn/upload/image_hosting/kb5g768u.png) “せやな~”是犬山葵的口头禅,可译为“系(是)呀~” 犬山葵特别喜欢吹牛(她在吹牛时会露出死鱼眼般的眼神)。 有一天,抚子学会了用主席树求区间第 $K$ 大: > 凛酱,凛酱,主席树看起来好厉害的亚子! ——抚子 > 唔姆... ——凛 > せやな~。其实呢,主席树不仅能求区间第 $K$ 大,还能求第 $K$ 大区间哦,前 $K$ 大区间和也可以的。 ——葵 > 真的吗?唔...不会哎。但凛酱一定会做!凛酱? ——抚子 > 我只想安安静静地喝茶啊... ——凛 凛不愿意浪费美好的下午茶时间,于是她找到了无所不能的您来帮忙。

题目描述

葵将会告诉您一个序列和 $K$ 的大小,您需要求出第 $K$ 大区间权值以及前 $K$ 大区间权值和(区间权值定义为序列中在这个区间内的整数之和)。 特别的,如果第 $K$ 大区间的权值出现了多次,只需要统计前 $K$ 个区间的权值和(即将所有区间按权值大小排序后取前 $K$ 个)。 请注意:抚子正在满怀期待地等着您,所以您必须在 $2s$ 之内解决这个问题。

输入输出格式

输入格式


第一行读入三个正整数 $n,K,op$,表示序列长度为 $n,K$ 意义如上,$op$ 见下方特殊性质 $2$ 。 第二行读入 $n$ 个整数表示序列 $a$ 。

输出格式


第一行输出一个整数表示第 $K$ 大区间的权值。 第二行输出一个整数表示前 $K$ 大一共 $K$ 个区间的权值和(如满足特殊性质 $2$ 则不需要输出第二行)。 第二行输出答案对 $99999999999999997$ $(10^{18}\!-\!3)$ 取模。

输入输出样例

输入样例 #1

10 5 1
9 -1 -9 -1 -6 -4 4 7 9 6

输出样例 #1

16
106

输入样例 #2

5 7 1
3 12 6 4 9

输出样例 #2

18
170

输入样例 #3

10 30 0
5 -78 15 43 -24 -45 57 88 29 -9

输出样例 #3

31

说明

[**【大样例】**](https://files.cnblogs.com/files/Xing-Ling/Seyana_Bigdata.rar) **【样例解释】** 对于样例一:一共有 $55$ 个区间,按权值从大到小排序后为:$[7,10],[6,10],[8,10],[7,9],[5,10],[6,9],[8,9],[4,10]...[2,6]$,其权值分别:$\{26\},\{22\},\{22\},\{20\},\{16\},\{16\},\{16\},\{15\}...\{-21\}$,所以第 $K$ 大区间权值为 $16$,前 $K$ 大区间权值和为:$26+22+22+20+16=106$。 **【数据范围】** $100 \%:$ $n \leqslant 10^5,$ $K \leqslant min(10^9,\frac{n(n+1)}{2}),$ $\mid a_{i}\! \mid \leqslant 10^9$ |测试点|$n$|$K$|$op$|特殊性质| | :------: |:------:|:------:|:------:|:------:| |$1,2$ |$n \leqslant 10^3$|$K \leqslant 10^3$|$op=1$|无| |$3,4,5$ |$n \leqslant 6*10^3$|$K \leqslant 10^3$|$op=1$|无| |$6,7,8$ |$n \leqslant 5*10^4$|$K \leqslant 10^3$|$op=1$|无| |$9,10$ |$n \leqslant 10^5$|$K \leqslant 5*10^5$|$op=1$|特殊性质 $1$| |$11,12,13,14$|$n \leqslant 10^5$|$K \leqslant 5*10^5$|$op=1$|无| |$15,16$ |$n \leqslant 10^5$|$K \leqslant 10^9$|$op=0$|特殊性质 $2$| |$17,18,19,20$|$n \leqslant 10^5$|$K \leqslant 10^9$|$op=1$|无| 特殊性质 $1$:$\forall i \in [1,n],$ $a_{i} \geqslant 0$ 。 特殊性质 $2$:只需要求输出 $K$ 大区间,不用输出前 $K$ 大区间的权值和。 $|a_{i}|$ 的大小在各段中都有一定分级。 本题做法较多,每段不同的数据范围都是有意义的!