Известный во всем мире астрофизик Млейл ваГрасс Тайсок недавно прочитал о существовании скоплений галактик-близнецов. Прежде чем поделиться этими знаниями с широкой аудиторией в своем подкасте под названием S.tarT-ok, он хочет доказать их существование самостоятельно. Млейл осознает, что просторы Вселенной поражают воображение (почти так же поражают, как и его наблюдательность), и решает попытать счастья и найти новое скопление галактик-близнецов.
Для этого он использует свой ТЛескоп для наблюдения за еще не исследованной человечеством частью ночного неба, в которой есть ровно \(2^{k + 1}\) галактик, расположенных в ряд. \(i\)-я из них состоит ровно из \(0 \le g_i < 4^k\) звезд.
Скопление галактик — это любой непустой непрерывный подотрезок галактик. Более того, считается, что её признак равен побитовому исключающему ИЛИ всех значений \(g_i\) в этом диапазоне.
Два скопления галактик считаются близнецами тогда и только тогда, когда они имеют равные признаки и их соответствующие отрезки не пересекаются.
Напишите программу, которая для многих сценариев будет читать описание участка ночного неба, наблюдаемого Млейлем, и выводить расположение двух отрезков, принадлежащих некоторой паре галактик-близнецов, или единственное значение \(-1\), если такой пары не существует.
Выходные данные
Ответы для всех наборов входных данных должны содержаться в отдельных строках. Если существует пара галактик-близнецов, то выведите четыре целых числа \(a\), \(b\), \(c\) и \(d\), обозначающие их отрезки \([a, b]\) и \([c, d]\) (первый интервал не обязан начинаться раньше второго, но они должны быть непересекающимися). Если пары таких галактик не существует, выведите единственное значение \(-1\).
Примечание
В первом наборе входных данных мы выбираем интервалы \([2, 4]\) и \([6, 6]\) в качестве наших галактик-близнецов. Признак первого интервала равен \(15 \oplus 0 \oplus 7 = 8\), и признак второго интервала равен \(8\), так что эти скопления галактик действительно являются близнецами.
Примеры
| № | Входные данные | Выходные данные |
|
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
|