T544700 氯化钠

小 y 喜欢在乐扣刷题，某一天做到了这样一个题 > 有一个长度为 $n$ 的数组 $a$，求出数组的所有子段和，并将这 $\frac{n(n+1)}{2}$ 个数降序排列，他想知道第 $k$ 个数有多大。 小 y 很快就解决了这个问题。但是小 y 觉得比起子段和，二元组的和更加美妙，比如 2Na(s)+Cl₂(g)→2NaCl(s)，于是小 y 决定将子段和改成子段中最大值与最小值的和。 小 y 有一个长度为 $n$ 的数组 $a$，定义 $\text{val}(l，r)=\min(a_l,a_{l+1},\dots,a_{r-1},a_r) + \max(a_l,a_{l+1},\dots,a_{r-1},a_r)$。 小 y 想知道对于所有的 $\text{val}(l,r)，1\le l\le r\le n$，降序排列后，第 $k$ 个数是多少，也就是第 $k$ 大的 $\text{val}$。

第一行一个正整数 $T$ ($T\le200$) 表示数据组数。 对于每组数据： 第一行输入三个整数 $n$ 和 $k$，$(1\le n\le10^5，1\le k\le \frac{n(n+1)}{2})$ 分别表示数组长度，要求第多少大的 $\text{val}$。 第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示 $a_i$ 的值。 $(0\le a_i\le 10^9)$ 保证 $\sum n=1064824$

对于每组数据，输出一个整数，表示所有的 $\text{val}(l,r)，1\le l\le r\le n$ 中，第 $k$ 大的 $\text{val}$ 的大小。