C2. Sheikh (Hard Version)time limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis 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.InputEach 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.OutputFor 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.ExampleInput
61 101 12 25 101 22 23 30 2 41 31 22 34 40 12 8 31 41 32 42 35 521 32 32 32 101 51 41 32 53 57 70 1 0 1 0 1 01 73 62 51 44 72 62 7Output
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
NoteIn 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.
61 101 12 25 101 22 23 30 2 41 31 22 34 40 12 8 31 41 32 42 35 521 32 32 32 101 51 41 32 53 57 70 1 0 1 0 1 01 73 62 51 44 72 62 7
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 
['binary search', 'bitmasks', 'brute force', 'greedy', 'implementation', 'two pointers', '*2100']