题目描述

有一个长度为 $n$ 的整数序列 $a_1,a_2,...,a_n$，序列中每个元素 $a_i$ 都在 $1\sim n$ 中等概率随机生成。

定义一个序列 $b_1,b_2,...,b_m$ 的价值 $\text{val}(b_1,b_2,...,b_m)$ 为其所有连续子序列的最大值的众数（即出现次数最大的数），当有多个众数时选择值最大的众数。

给出 $q$ 次询问，每次询问给定两个整数 $l,r$，问 $\text{val}(a_l,a_{l+1},...,a_r)$。

输入格式

本题单个测试点内包含多组测试数据。

第一行一个整数 $T$（$1\le T\le 3$），表示数据组数。

对于每组数据，第一行两个整数 $n,q$（$1\le n,q \le2\times10^5$），分别表示序列长度和询问次数。

第二行 $n$ 个整数 $a_1,a_2,...,a_n$（$1\le a_i \le n$），表示序列。

接下来 $q$ 行，每行两个整数 $l_i,r_i$（$1\le l_i \le r_i \le n$），表示一次询问。

输出格式

对于每组数据，由于输出很大，假设原来第 $i$ 个询问的答案是 $x_i$，你只需要输出一行一个整数：

即 $i$ 和 $x_i$ 乘积的异或和即可。

输入样例

1
5 3
1 2 2 1 3
1 5
2 3
3 5

输出样例

15

提示

三次询问的答案分别为 $2, 2, 3$。