CF1732C2.Sheikh (Hard Version)

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$.

这是该问题的困难版本。唯一的区别在于本版本中 $q = n$。

给你一个整数数组 $a_1, a_2, \ldots, a_n$。

数组的一个子段 $[l, r]$（其中 $1 \leq l \leq r \leq n$）的代价定义为值 $f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)$，其中 $\operatorname{sum}(l, r) = a_l + a_{l+1} + \ldots + a_r$，而 $\operatorname{xor}(l, r) = a_l \oplus a_{l+1} \oplus \ldots \oplus a_r$（$\oplus$ 表示按位异或）。

你将收到 $q$ 个查询。每个查询由一对数 $L_i$, $R_i$ 给出，满足 $1 \leq L_i \leq R_i \leq n$。你需要在满足 $L_i \leq l \leq r \leq R_i$ 的所有子段 $[l, r]$ 中，找出使 $f(l, r)$ 最大的那个子段。若存在多个这样的子段，则需在其中选出长度最小者，即 $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 = 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$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 10^5$，$q = n$），分别表示数组长度和查询次数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 10^9$），即数组元素。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $L_i$ 和 $R_i$（$1 \leq L_i \leq R_i \leq n$），表示需要查找的区间的左右边界。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

保证 $L_1 = 1$ 且 $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.

对每个测试用例，输出 $q$ 对数字 $L_i \leq l \leq r \leq R_i$，使得函数值 $f(l, r)$ 达到最大；在所有使 $f(l, r)$ 最大的区间中，要求长度 $r - l + 1$ 最小。若存在多个正确答案，输出任意一个即可。

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.

在所有测试用例中，仅考虑第一个查询。

在第一个测试用例中，$f(1, 1) = 0 - 0 = 0$。

在第二个测试用例中，$f(1, 1) = 5 - 5 = 0$，$f(2, 2) = 10 - 10 = 0$。注意 $f(1, 2) = (10 + 5) - (10 \oplus 5) = 0$，但我们需要在所有使 $f(l, r)$ 取得最大值的子段中，找出长度最短者。因此，只有子段 $[1, 1]$ 和 $[2, 2]$ 是正确答案。

在第四个测试用例中，$f(2, 3) = (12 + 8) - (12 \oplus 8) = 16$。

第五个测试用例中有两个正确答案，因为 $f(2, 3) = f(3, 4)$，且它们的长度相等。