Алексей Юрьевич и Михаил Леонидович отправились на поезде в Троицк. По дороге к ним подсели вахтовик и дембель. После знакомства и небольших историй о себе вахтовик и дембель решили устроить Алексею Юрьевичу и Михаилу Леонидовичу тест «на мужика»: нужно решить непростую задачку по программированию.
Помогите Алексею Юрьевичу и Михаилу Леонидовичу пройти тест «на мужика».
Задан массив целых чисел a
1,a
2,...,a
n.
Стоимостью подотрезка массива 1 <= l <= r <= n назовем величину f(l,r) = sum(l,r) − xor(l,r), где sum(l,r) = a
l +a
l+1+...+a
r, а xor(l,r) = a
l ⊕a
l+1 ⊕...⊕a
r (⊕ здесь обозначает операцию XOR, побитовое исключающее «ИЛИ» чисел, подробнее в разделе «Замечание»).
Требуется найти подотрезок заданного массива с максимальным значением f(l,r). Если ответов несколько, то среди них нужно найти подотрезок с минимальной длиной, то есть минимальным значением r − l +1.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число t (1 <= t <= 10
4) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число n (1 <= n <= 10
5) — длину массива.
Вторая строка каждого набора входных данных содержит n целых чисел a
1,a
2,...,a
n (0 <= a
i <= 10
9) — элементы массива.
Гарантируется, что сумма n по всем наборам входных данных не превосходит 2 · 10
5.
Выходные данные
Для каждого набора входных данных выведите два числа 1 <= l <= r <= n таких, что значение f(l,r) максимально по всем подотрезкам массива a, а длина r −l +1 минимальна. Если существует несколько правильных ответов, выведите любой из них.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6
1
0
2
5 10
3
0 2 4
4
0 12 8 3
5
21 32 32 32 10
7
0 1 0 1 0 1 0 |
1 1
2 2
3 3
2 3
3 4
4 6 |
Замечание
Операция XOR двух чисел a и b — это битовая операция, которая применяется независимо к каждой паре соответствующих битов a и b. Эта операция представляет собой сложение по модулю 2. Вот её таблица истинности для пары битов:
| a |
b |
a⊕b |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
0 |
В первом наборе входных данных f(1,1) = 1 − 1 = 0.
Во втором наборе входных данных f(2,2) = 10 − 10 = 0. Заметим, что f(1,2) = (10 + 5) − (10 ⊕ 5) = 0, но нам среди максимальных значений f(l,r) нужно найти подотрезок с минимальной длиной.
В четвертом наборе входных данных f(2,3) = (12+8) − (12 ⊕ 8) = 16.
В пятом наборе входных данных есть два правильных ответа, так как f(2,3) = f(3,4) и их длины равны.