C1. Шейх (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Единственное различие состоит в том, что в этой версии $$$q = 1$$$.

Вам дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$.

Стоимостью подотрезка массива $$$[l, r]$$$, $$$1 \leq l \leq r \leq n$$$, назовем величину $$$f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)$$$, где $$$\operatorname{sum}(l, r) = a_l + a_{l+1} + \ldots + a_r$$$, а $$$\operatorname{xor}(l, r) = a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$$$ ($$$\oplus$$$ обозначает побитовое исключающее ИЛИ).

У вас будет $$$q = 1$$$ запрос. Каждый запрос задается парой чисел $$$L_i$$$, $$$R_i$$$, где $$$1 \leq L_i \leq R_i \leq n$$$. Вам нужно найти подотрезок $$$[l, r]$$$, $$$L_i \leq l \leq r \leq R_i$$$ с максимальным значением $$$f(l, r)$$$. Если подходящих ответов несколько, то среди них нужно найти подотрезок с минимальной длиной, то есть минимальным значением $$$r - l + 1$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n \leq 10^5$$$, $$$q = 1$$$) — длину массива и количество запросов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — элементы массива.

$$$i$$$-я из следующих $$$q$$$ строк каждого набора входных данных содержит два целых числа $$$L_i$$$ и $$$R_i$$$ ($$$1 \leq L_i \leq R_i \leq n$$$) — границы, в которых нужно найти отрезок.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Гарантируется, что $$$L_1 = 1$$$ и $$$R_1 = n$$$.

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

Для каждого набора входных данных выведите $$$q$$$ пар чисел $$$L_i \leq l \leq r \leq R_i$$$, таких что значение $$$f(l, r)$$$ максимально, а среди таких длина $$$r - l + 1$$$ минимальна. Если существует несколько правильных ответов, выведите любой из них.

Пример
Входные данные
6
1 1
0
1 1
2 1
5 10
1 2
3 1
0 2 4
1 3
4 1
0 12 8 3
1 4
5 1
21 32 32 32 10
1 5
7 1
0 1 0 1 0 1 0
1 7
Выходные данные
1 1
1 1
1 1
2 3
2 3
2 4
Примечание

В первом наборе входных данных $$$f(1, 1) = 0 - 0 = 0$$$.

Во втором наборе входных данных $$$f(1, 1) = 5 - 5 = 0$$$, $$$f(2, 2) = 10 - 10 = 0$$$. Заметим, что $$$f(1, 2) = (10 + 5) - (10 \oplus 5) = 0$$$, но нам среди максимальных значений $$$f(l, r)$$$ нужно найти подотрезок с минимальной длиной. Поэтому правильными ответами будут только отрезки $$$[1, 1]$$$ и $$$[2, 2]$$$.

В четвертом наборе входных данных $$$f(2, 3) = (12 + 8) - (12 \oplus 8) = 16$$$.

В пятом наборе входных данных есть два правильных ответа, так как $$$f(2, 3) = f(3, 4)$$$ и их длины равны.