Sheikh (Hard Version)
Contest: Codeforces Round 830 (Div. 2)
Difficulty rating: 2100
Tags: binary search, bitmasks, brute force, greedy, implementation, two pointers

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

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$$$ queries. 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 = n$$$) — 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 all test cases, the first query is considered.

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 2
5 10
1 2
2 2
3 3
0 2 4
1 3
1 2
2 3
4 4
0 12 8 3
1 4
1 3
2 4
2 3
5 5
21 32 32 32 10
1 5
1 4
1 3
2 5
3 5
7 7
0 1 0 1 0 1 0
1 7
3 6
2 5
1 4
4 7
2 6
2 7

Example output:
1 1
1 1
2 2
1 1
1 1
2 2
2 3
2 3
2 3
2 3
2 3
2 3
2 3
2 3
3 4
2 4
4 6
2 4
2 4
4 6
2 4
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$$$. From this we obtain that the maximum value of $$$f$$$ is reached on the entire subsegment.
Next, let's see in which case $$$xor$$$ changes exactly by $$$x$$$, because if it changes by a smaller value, then $$$f(l, r)$$$ will be strictly less than $$$f(l, r + 1)$$$. The value of $$$xor$$$ will change exactly by $$$x$$$ if all 1 bits of $$$x$$$ were zeros in the current $$$xor$$$. In fact, this means that if we consider the first $$$\log A + 1$$$ non-zero element, then at least one of the bits will occur twice, and thus the value of the function will become smaller.
Let's put all these facts together: we can remove at most $$$\log A + 1= 30 + 1= 31$$$ non-zero element from the beginning and end of the subsegment. Then let's just iterate over how many non-zero elements we remove on the prefix and suffix (their positions can be found using binary search) and using prefix sums and $$$xor$$$-s, calculate the value on this subsegment.