众数

Problem Description

有一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$，序列中每个元素 $a_i$ 都在 $1\sim n$ 中等概率随机生成。 定义一个序列 $b_1,b_2,\cdots,b_m$ 的价值 $\operatorname{val}(b_1,b_2,\cdots,b_m)$ 为其所有连续子序列的最大值的众数（即出现次数最大的数），当有多个众数时选择值最大的众数。 给出 $q$ 次询问，每次询问给定两个整数 $l,r$，问 $\operatorname{val}(a_{l},a_{l+1},\cdots,a_r)$。

Input

本题单个测试点内包含多组测试数据。 第一行一个整数 $T(1\leq T\leq 3)$，表示数据组数。 对于每组数据，第一行两个整数 $n,q$ $(1\leq n,q\leq 2\times 10^5)$，分别表示序列长度和询问次数。 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ $(1\leq a_i\leq n)$，表示序列。 接下来 $q$ 行，每行两个整数 $l_i,r_i$ $(1\leq l_i\leq r_i\leq n)$，表示一次询问。

Output

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

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

Sample Input

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

Sample Output

15

Hint

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

Source

2024“钉耙编程”中国大学生算法设计超级联赛（1）