3047: The K-th Largest Interval

We define a value of an interval is the second largest number of it's elements, and of course an interval has at least two elements.

Given an array $A$ with $n$ elements and a number $k$, can you find the value of the $k^{th}$ largest interval?

The first line contains an integer number $T$, the number of test cases.

For each test case :
The first line contains two integer numbers $n, k(2 \leq n \leq 10^{5}, 1 \leq k \leq \frac{n(n-1)}{2})$, the number of test cases.

The second lines contains $n$ integers $A_{i}(1 \leq A_{i} \leq 10^{9})$, the elements of array $A$.

For each test case print the value of  the $k^{th}$ largest interval.

2
3 3
1 2 3
5 1
1 2 2 3 3

1
3