你有一个包含 $N$ 个整数的数组 $A$，$A[1], A[2], \dots, A[N]$。给定 $Q$ 次查询，每次查询包含两个整数 $L$ 和 $R$。考虑一个长度为 $R - L + 1$ 的新数组 $B$，满足对于所有 $1 \le i \le R - L + 1$，都有 $B[i] = A[L + i - 1]$。在一次操作中，你可以按顺序执行以下步骤：

1. 选择一个下标 $j$，满足 $1 \le j \le R - L + 1$。
2. 选择一个整数 $i$，满足 $2^i \le B[j]$。
3. 将 $B[j]$ 替换为 $B[j] \oplus (B[j] - 2^i)$，其中 $\oplus$ 表示按位异或运算符。

对于每次查询，答案是 $B$ 中所有元素按位或（OR）的最大可能值，以及获得该值所需的最少操作次数。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。接下来是各测试用例。 每个测试用例的第一行包含两个整数 $N$ 和 $Q$。 第二行包含 $N$ 个空格分隔的整数 $A[1], A[2], \dots, A[N]$。 接下来的 $Q$ 行，每行包含两个空格分隔的整数 $L$ 和 $R$。

数据范围

• $1 \le T \le 10^5$
• $1 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $0 \le A[i] \le 10^9$
• $1 \le L \le R \le N$
• 所有测试用例中 $N$ 的总和不超过 $10^5$
• 所有测试用例中 $Q$ 的总和不超过 $10^5$

输出格式

对于每个测试用例，打印 $Q$ 行，每行包含两个空格分隔的整数，分别表示最大可能的按位或值以及所需的最少操作次数。

样例

输入 1

1
3 2
10 10 5
1 2
1 3

输出 1

15 2
15 0