U102004 せやな～

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

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

无

无

[**【大样例】**](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}|$ 的大小在各段中都有一定分级。 本题做法较多，每段不同的数据范围都是有意义的！