codeforces#P1983F. array-value

    ID: 34732 远端评测题 4000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchbitmasksdata structuresgreedytwo pointers

array-value

Description

You have an array of non-negative integers $a_1, a_2, \ldots, a_n$.

The value of a sub-array of length $\ge 2$, $a[l, r] = [a_l, a_{l+1}, \ldots, a_r]$ is the minimum value of $a_i \oplus a_j$ such that $l \le i < j \le r$, where $\oplus$ is the xor (exclusive-or) operator.

You have to find the $k$-th smallest value over all sub-arrays of length $\ge 2$.

The first line of the input contains multiple test cases $t$ ($1 \le t \le 2 \cdot 10^4$).

The first line of each test case contains integer numbers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le \frac{n\cdot(n-1)}{2}$).

The second line of the input contains $n$ non-negative integer numbers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the array itself.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Print the $k$-th smallest value obtained over all subarrays of length at least $2$.

Input

The first line of the input contains multiple test cases $t$ ($1 \le t \le 2 \cdot 10^4$).

The first line of each test case contains integer numbers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le \frac{n\cdot(n-1)}{2}$).

The second line of the input contains $n$ non-negative integer numbers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the array itself.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

Print the $k$-th smallest value obtained over all subarrays of length at least $2$.

4
5 2
1 2 3 4 5
2 1
4 3
4 6
1 2 4 8
5 9
1 2 3 4 5
1
7
12
3

Note

In the first testcase, we have subarrays with their smallest exclusive-or pair as:

$[1,2]: 3$

$[2,3]: 1$

$[3,4]: 7$

$[4,5]: 1$

$[1,2,3]: 1$

$[2,3,4]: 1$

$[3,4,5]: 1$

$[1,2,3,4]: 1$

$[2,3,4,5]: 1$

$[1,2,3,4,5]: 1$

The sorted order would be: $1, 1, 1, 1, 1, 1, 1, 1, 3, 7$. Therefore, the second smallest element would be $1$.