B'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 <= q l <= q r <= q 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 <= q L_i <= q R_i <= q n . You need to find the subsegment [l, r] , L_i <= q l <= q r <= q 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 <= q t <= q 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 <= q n <= q 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 <= q a_i <= q 10^9 ) -- array elements. i -th of the next q lines of each test case contains two integers L_i and R_i ( 1 <= q L_i <= q R_i <= q 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 <= q l <= q r <= q 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 all'...