C1. Sheikh (Easy version)
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\).
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\).
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.
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.