Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Лиза и марсиане
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Девочку Лизу похитили марсиане! Не беда, ведь она смотрела много телепередач про инопланетян, поэтому знает, что её ждёт. Назовём число марсианским, если оно является целым неотрицательным и строго меньше $$$2^k$$$, например, при $$$k = 12$$$, числа $$$51$$$, $$$1960$$$, $$$0$$$ — марсианские, а числа $$$\pi$$$, $$$-1$$$, $$$\frac{21}{8}$$$, $$$4096$$$ — нет.

Инопланетяне выдадут Лизе $$$n$$$ марсианских чисел $$$a_1, a_2, \ldots, a_n$$$. Затем они попросят её назвать любое марсианское число $$$x$$$. После чего Лиза выберет в выданной последовательности пару чисел $$$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)$$$ должно быть максимально возможным.

Если решений несколько, вы можете вывести любое.

Пример
Входные данные
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 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$$$.