C. Галактики-близнецы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Известный во всем мире астрофизик Млейл ваГрасс Тайсок недавно прочитал о существовании скоплений галактик-близнецов. Прежде чем поделиться этими знаниями с широкой аудиторией в своем подкасте под названием S.tarT-ok, он хочет доказать их существование самостоятельно. Млейл осознает, что просторы Вселенной поражают воображение (почти так же поражают, как и его наблюдательность), и решает попытать счастья и найти новое скопление галактик-близнецов.

Для этого он использует свой ТЛескоп для наблюдения за еще не исследованной человечеством частью ночного неба, в которой есть ровно $$$2^{k + 1}$$$ галактик, расположенных в ряд. $$$i$$$-я из них состоит ровно из $$$0 \le g_i < 4^k$$$ звезд.

Скопление галактик — это любой непустой непрерывный подотрезок галактик. Более того, считается, что её признак равен побитовому исключающему ИЛИ всех значений $$$g_i$$$ в этом диапазоне.

Два скопления галактик считаются близнецами тогда и только тогда, когда они имеют равные признаки и их соответствующие отрезки не пересекаются.

Напишите программу, которая для многих сценариев будет читать описание участка ночного неба, наблюдаемого Млейлем, и выводить расположение двух отрезков, принадлежащих некоторой паре галактик-близнецов, или единственное значение $$$-1$$$, если такой пары не существует.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$k$$$ ($$$0 \le k \le 17$$$).

Вторая строка содержит $$$2^{k + 1}$$$ целых чисел $$$g_1, g_2, \ldots, g_{2^{k+1}}$$$ ($$$0 \le g_i < 4^k$$$).

Гарантируется, что сумма значений $$$2^{k + 1}$$$ по всем наборам входных данных не превосходит $$$2^{18}$$$.

Выходные данные

Ответы для всех наборов входных данных должны содержаться в отдельных строках. Если существует пара галактик-близнецов, то выведите четыре целых числа $$$a$$$, $$$b$$$, $$$c$$$ и $$$d$$$, обозначающие их отрезки $$$[a, b]$$$ и $$$[c, d]$$$ (первый интервал не обязан начинаться раньше второго, но они должны быть непересекающимися). Если пары таких галактик не существует, выведите единственное значение $$$-1$$$.

Пример
Входные данные
4
2
4 15 0 7 11 8 3 2
1
0 1 2 3
0
0 0
3
15 63 57 39 61 25 42 61 50 41 27 41 56 23 17 27
Выходные данные
2 4 6 6
2 2 3 4
1 1 2 2
1 1 4 10
Примечание

В первом наборе входных данных мы выбираем интервалы $$$[2, 4]$$$ и $$$[6, 6]$$$ в качестве наших галактик-близнецов. Признак первого интервала равен $$$15 \oplus 0 \oplus 7 = 8$$$, и признак второго интервала равен $$$8$$$, так что эти скопления галактик действительно являются близнецами.