Sheikh (Easy version)
Contest: Codeforces Round 830 (Div. 2)
Difficulty rating: 1800
Tags: binary search, bitmasks, greedy, two pointers

This is the easy version of the problem. The only difference is that in this version $$$q = 1$$$.

You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$.

The cost of a subsegment of the array $$$[l, r]$$$, $$$1 \leq l \leq r \leq n$$$, is the value $$$f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)$$$, where $$$\operatorname{sum}(l, r) = a_l + a_{l+1} + \ldots + a_r$$$, and $$$\operatorname{xor}(l, r) = a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$$$ ($$$\oplus$$$ stands for bitwise XOR).

You will have $$$q = 1$$$ query. Each query is given by a pair of numbers $$$L_i$$$, $$$R_i$$$, where $$$1 \leq L_i \leq R_i \leq n$$$. You need to find the subsegment $$$[l, r]$$$, $$$L_i \leq l \leq r \leq R_i$$$, with maximum value $$$f(l, r)$$$. If there are several answers, then among them you need to find a subsegment with the minimum length, that is, the minimum value of $$$r - l + 1$$$.

Input format:
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n \leq 10^5$$$, $$$q = 1$$$) — the length of the array and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — array elements.

$$$i$$$-th of the next $$$q$$$ lines of each test case contains two integers $$$L_i$$$ and $$$R_i$$$ ($$$1 \leq L_i \leq R_i \leq n$$$) — the boundaries in which we need to find the segment.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

It is guaranteed that $$$L_1 = 1$$$ and $$$R_1 = n$$$.

Output format:
For each test case print $$$q$$$ pairs of numbers $$$L_i \leq l \leq r \leq R_i$$$ such that the value $$$f(l, r)$$$ is maximum and among such the length $$$r - l + 1$$$ is minimum. If there are several correct answers, print any of them.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$f(1, 1) = 0 - 0 = 0$$$.

In the second test case, $$$f(1, 1) = 5 - 5 = 0$$$, $$$f(2, 2) = 10 - 10 = 0$$$. Note that $$$f(1, 2) = (10 + 5) - (10 \oplus 5) = 0$$$, but we need to find a subsegment with the minimum length among the maximum values of $$$f(l, r)$$$. So, only segments $$$[1, 1]$$$ and $$$[2, 2]$$$ are the correct answers.

In the fourth test case, $$$f(2, 3) = (12 + 8) - (12 \oplus 8) = 16$$$.

There are two correct answers in the fifth test case, since $$$f(2, 3) = f(3, 4)$$$ and their lengths are equal.

Example input:
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

Example output:
1 1
1 1
1 1
2 3
2 3
2 4

Editorial:
Note that $$$f(l, r) \leq f(l, r + 1)$$$. To prove this fact, let's see how the sum and xor change when the element $$$x$$$ is added. The sum will increase by $$$x$$$, but $$$xor$$$ cannot increase by more than $$$x$$$.
Then it was possible to use two pointers or binary search to solve the problem. If you solve the problem in the second way, then you iterate over the right boundary of the answer and look for the optimal left boundary for it by binary search. You will need $$$O(1)$$$ to find the sum on the segment and xor on the segment. To do this, you can use prefix sums and prefix xor.