解题思路

设区间 $[l,r]$ 的函数值为：

也就是说，$f(l,r)$ 是区间 $[l,r]$ 内所有“从左端点开始的前缀和”之和。

题目内容

给定一个长度为$n$的整数序列$a_1, a_2, \dots, a_n$。定义

$f(l, r) = \sum_{i=l}^{r} \left( \sum_{t=l}^{i} a_t \right)$

例如$a = \{1, 2, 2, 3\}，l=1, r=3$：

$(f(1, 3) = \sum_{i=1}^{3} \left( \sum_{t=1}^{i} a_t \right) = (1) + (1+2) + (1+2+2) = 1 + 3 + 5 = 9$

现要求在所有$n(n+1)/2$个区间中，按数值从小到大排序（数值相同按出现次数计入多次），输出第 $k$小的 $(f(l, r)$ 的值。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\ (1 \le T \le 10^5)$代表数据组数，每组测试数据描述如下：

• 第一行输入两个整数$n, k (\left(1 \le n \le 2 \times 10^5,\ 1 \le k \le \dfrac{n(n+1)}{2}\right)$；
• 第二行输入 $n$ 个整数$a_1, a_2, \dots, a_n\ (0 \le a_i \le 10^6)$。

保证所有测试中 $n$的总和不超过 $5 \times 10^5$。

输出描述

对于每组测试数据，输出一个整数，表示所有区间中第 $k$ 小的$f(l, r)$的值。

样例1

输入

2
3 2
1 2 3
3 4
2 0 1

输出

2
2

说明

样例一：所有区间及$f$值为

$[1,1] \to 1,\ [1,2] \to 4,\ [1,3] \to 10,\ [2,2] \to 2,\ [2,3] \to 7,\ [3,3] \to 3$。

从小到大排序为$1, 2, 3, 4, 7, 10$，第 $2$ 小为 $2$。

样例二：$f$ 值从小到大排序为 $0, 1, 1, 2, 4, 7$，第 $4$ 小为 $2$