← 返回题目列表

Codeforces · 1983/F

F. 数组值

中文机器翻译题面 查看原题

你有一个非负整数数组 $$$a_1, a_2, \ldots, a_n$$$。

长度为 $$$\ge 2$$$ 的子数组的值,$$$a[l, r] = [a_l, a_{l+1}, \ldots, a_r]$$$ 是 $$$a_i \oplus a_j$$$ 的最小值,使得 $$$l \le i < j \le r$$$,其中 $$$\oplus$$$ 是xor(异或)运算符。

您必须在长度为 $$$\ge 2$$$ 的所有子数组中找到第 $$$k$$$ 个最小值。

输入

输入的第一行包含多个测试用例 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$)。

每个测试用例的第一行包含整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le \frac{n\cdot(n-1)}{2}$$$)。

输入的第二行包含 $$$n$$$ 非负整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 数组本身。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

打印在长度至少为 $$$2$$$ 的所有子数组中获得的第 $$$k$$$ 最小值。

示例

输入 #1

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

1
7
12
3

注意

在第一个测试用例中,我们的子数组的最小异或对如下:

$$$[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$$$

排序顺序为:$$$1, 1, 1, 1, 1, 1, 1, 1, 3, 7$$$。因此,第二小的元素将是 $$$1$$$。