题目内容

某工厂有一条由 $n$ 个工位组成的流水线，工位依次编号为 $1$ 到 $n$，每个工位 $i$ 的处理时间为一个非负整数 $a_i$。

对于一段连续的工位 $[l, r]$（$1 \le l \le r \le n$），定义它的加权成本为：

即该区间内每个位置的前缀和（从 $l$ 开始到当前位置的累计处理时间）之和。

流水线上共有 $\frac{n(n+1)}{2}$ 个不同的连续工位区间。将这些区间的加权成本按数值从小到大排序，数值相同的视为不同区间，重复计入次序。请输出其中第 $k$ 小的成本值。

数据规模与约定：

• 每组数据的工位数 $n$ 满足 $1 \le n \le 2 \times 10^5$。
• 名次 $k$ 满足 $1 \le k \le \frac{n(n+1)}{2}$。
• 每个工位的处理时间 $a_i$ 满足 $0 \le a_i \le 10^6$。
• 所有测试数据中 $n$ 的总和不超过 $5 \times 10^5$。

输入描述

第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试数据组数。 接下来依次描述每组数据：

• 第一行包含两个整数 $n$ 和 $k$，分别表示工位数量和需要查找的名次。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个工位的处理时间。

输出描述

对于每组测试数据，输出一行一个整数，表示所有区间加权成本中第 $k$ 小的数值。

样例1

输入

3
1 1
7
3 4
0 2 0
2 2
5 3

输出

7
2
5

说明

共 3 组测试数据。

第一组：只有 1 个工位，处理时间 $a=[7]$。唯一的区间 $[1,1]$ 的加权成本为 $cost(1,1)=7$。总区间数为 $1$，因此第 1 小的值就是 7。

第二组：$n=3$，$a=[0,2,0]$。所有连续区间的加权成本由 $cost(l,r)=\sum_{i=l}^r (r-i+1)a_i$ 计算：

• $[1,1]$：$0$
• $[1,2]$：$0\times 2 + 2\times 1 = 2$
• $[1,3]$：$0\times 3 + 2\times 2 + 0\times 1 = 4$
• $[2,2]$：$2$
• $[2,3]$：$2\times 2 + 0\times 1 = 4$
• $[3,3]$：$0$

将上述 6 个成本排序：$0, 0, 2, 2, 4, 4$。第 4 小的数值为 2。

第三组：$n=2$，$a=[5,3]$。区间成本为：

• $[1,1]$：$5$
• $[1,2]$：$5\times 2 + 3\times 1 = 13$
• $[2,2]$：$3$

排序后为 $3, 5, 13$，第 2 小即为 5。