I. Permátomo tasters (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. Note that the only difference in the problems are the constraints over $$$N$$$, $$$K$$$ and $$$T$$$.

Mari and Klaus are a beautiful couple who love mathematics. They also share a very particular passion: they are Permátomo tasters. The Permátomo is an abstract object that represents the combinatorial essence of couples, and Mari and Klaus enjoy experimenting with it in creative ways. Today, they are looking to obtain the k-th best couple of the Permátomo.

Formally, given an array of size N, Mari and Klaus want to compute the sum of all possible pairs $$$(i, j)$$$ where $$$1 \leq i, j \leq N$$$. For each such pair $$$(i, j)$$$ they calculate: $$$s_k = a_i + a_j$$$ where $$$k$$$ corresponds to the number of the couple created. In total, there are exactly $$$N^2$$$ possible couples.

Then, Mari and Klaus ask themselves: What is the k-th best couple of the Permátomo? For Permátomo tasters, this means finding the k-th smallest sum among all possible sums $$$s_k$$$.

Input

The input contains several test cases.

The first line contains an integer T $$$(1 \leq T \leq 3)$$$, the number of test cases.

Each test case has the following format:

  • A line with two integers N and K $$$(1 \leq N \leq 100000,\ 1 \leq K \leq N^2)$$$.
  • A line with N integers $$$a_1, a_2, \dots, a_N$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$.
Output

For each test case, print a single integer: the k-th best couple of the Permátomo, that is, the k-th smallest sum among all the possible sums of couples.

Example
Input
2
3 4
1 3 5
2 2
-1 2
Output
6
1