← 返回题目列表

Codeforces · 1851/F

F. 丽莎和火星人

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

丽莎被火星人绑架了!没关系,因为她看过很多有关外星人的电视节目,所以她知道等待着她的是什么。如果它是一个非负整数并且严格小于 $$$2^k$$$,我们称其为火星整数,例如,当 $$$k = 12$$$ 时,数字 $$$51$$$、$$$1960$$$、$$$0$$$ 是火星数字,而数字 $$$\pi$$$、$$$-1$$$、$$$\frac{21}{8}$$$、 $$$4096$$$ 不是。

外星人会给丽莎 $$$n$$$ 火星数字 $$$a_1, a_2, \ldots, a_n$$$。然后他们会要求她说出任何火星数字$$$x$$$。之后,Lisa 会按照给定的序列选择一对数字 $$$a_i, a_j$$$ ($$$i \neq j$$$) 并计数 $$$(a_i \oplus x) \& (a_j \oplus x)$$$。运算$$$\oplus$$$ 表示按位异或,运算$$$\&$$$ 表示按位与。例如,$$$(5 \oplus 17) \& (23 \oplus 17) = (00101_2 \oplus 10001_2) \& (10111_2 \oplus 10001_2) = 10100_2 \& 00110_2 = 00100_2 = 4$$$。

丽莎确信计算值越高,她回家的机会就越大。帮助女孩选择这样的 $$$i, j, x$$$ 使计算值最大化。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行描述。

第一行包含整数 $$$n, k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 30$$$) — 火星数字序列的长度和 $$$k$$$ 的值。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^k$$$) - 火星数字序列。

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

输出

对于每个测试用例,打印三个整数 $$$i, j, x$$$ ($$$1 \le i, j \le n$$$, $$$i \neq j$$$, $$$0 \le x < 2^k$$$)。 $$$(a_i \oplus x) \& (a_j \oplus x)$$$ 的值应该是可能的最大值。

如果有多种解决方案,您可以打印任何一种。

示例

输入 #1

10
5 4
3 9 1 4 13
3 1
1 0 1
6 12
144 1580 1024 100 9 13
4 3
7 3 0 4
3 2
0 0 1
2 4
12 2
9 4
6 14 9 4 4 4 5 10 2
2 1
1 0
2 4
11 4
9 4
2 11 10 1 6 9 11 0 5

输出 #1

1 3 14
1 3 0
5 6 4082
2 3 7
1 2 3
1 2 15
4 5 11
1 2 0
1 2 0
2 7 4

注意

第一个测试用例:$$$(3 \oplus 14) \& (1 \oplus 14) = (0011_2 \oplus 1110_2) \& (0001_2 \oplus 1110_2) = 1101_2 = 1101_2 \& 1111_2 = 1101_2 = 13$$$。

第二个测试用例:$$$(1 \oplus 0) \& (1 \oplus 0) = 1$$$。

第三个测试用例:$$$(9 \oplus 4082) \& (13 \oplus 4082) = 4091$$$。

第四个测试用例:$$$(3 \oplus 7) \& (0 \oplus 7) = 4$$$。