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

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

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

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

第一行一个整数 $T(1 ≤ T ≤ 3)$，表示数据组数。

对于每组数据，第一行两个整数 $n,q (1 ≤ n, q ≤ 2 ×10^5)$，分别表示序列长度和询问次数。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n ( 1 ≤ a_i ≤ n)$，表示序列。

接下来 $q$ 行，每行两个整数 $l_i,r_i (1 ≤ l_i ≤ r_i ≤ n)$，表示一次询问。

对于每组数据，由于输出很大，假设原来第 $i$ 个询问的答案是 $x_i$，你只需要输出一行一个整数：
$⨁_{i=1}^q i⋅x_i$

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

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