题目描述

众所周知，基因与人类密切相关，那么本题来谈谈关于夯基的那部分。

夯基，是大力出的奇基，存在着一些神秘的性质。

如果有两个基因的编号相同，那么这两个基因属于同种基因。

假设有一个连续的基因序列，对于任意一个连续的子基因片段，我们称它的夯基为出现次数最多，且编号最小的基因。

御坂在一次任务期间偶然得到了一个珍贵的基因序列，木山知道后便问了她几个问题，每次诸如询问一个子基因片段的夯基是那个。

御坂当然答不出来啦，于是来寻求夯水手，也就是你的帮助。

输入格式

第一行一个整数 $T$，表示测试点编号。

第二行两个整数 $n , m$，分别表示基因序列长度和询问次数。

第三行有 $n$ 个整数，表示基因序列的每一个基因的编号。

接下来 $m$ 行，每行诸如两个整数 $l$ 和 $r$，表示询问基因序列的 $[l,r]$ 子基因片段的夯基是哪个。

输出格式

首先对于每一个询问将答案输出到一行，用空格分开（最后一个询问之后不输出空格）

由于御坂不想看这么多的数据，所以需要你告诉她这个值：将所有的询问答案按照询问顺序进行排序，可以得到一个序列（先询问的在前），然后你需要输出 (对于所有的连续子序列$[l,r],l \le r$) $ ((\text{bitand}_{i=l}^{r}a_{i})+(\sum_{i=l}^{r}a_{i}))_{\text{max}} $ 。

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

3 3 3 4 3
16

数据范围与提示

约定：$n$ 表示数列长度，$m$ 表示询问次数，$M$ 表示值域，$a$ 序列是夯基的编号序列

保证数据随机、合法。

第 $1$ 个测试点 $n = 10$, $m = 10$, $M = 10$

第 $2$ 个测试点 $n = 100$, $m = 100$,$M = 100$

第 $3$ 个测试点 $n = 50000,m = 50000, M = 50000$ 特殊性质1

第 $4,5,6$ 个测试点 $n = 50000, m = 50000, M = 50000$

第 $7$ 个测试点 $n = 200000,m = 200000,M = 200000$ 特殊性质2

第 $8,9,10$ 个测试点 $n = 500000, m = 500000, M = 500000$ 特殊性质3

特殊性质 $1$：保证将查询区间按照右端点升序排序之后，左端点递增

特殊性质 $2$：对于任意两个询问区间 $[l,r]$ 和 $[x,y]$，要么不相交，要么 $l < x \le y \le r$，要么 $x < l \le r \le y$ 。

特殊性质 $3$：对于任意两个询问区间 $[l,r]$ 和 $[x,y]$，要么不相交，要么 $l \le x \le y \le r$，要么 $x \le l \le r \le y$ 。

对于所有数据，保证 $ 1 \le n, m \le 5\times 10^5, 1 \le a_i \le n, 1 \le l \le r \le n $。