题目描述

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

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

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

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

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

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

输入格式

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

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

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

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

输出格式

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

由于御坂不想看这么多的数据，所以需要你告诉她这个值：将所有的询问答案按照询问顺序进行排序，可以得到一个序列（先询问的在前），然后你需要输出

$$\max_{1 \le l \le r \le m} \left[ \left( \text{bitand}_{i=l}^{r} a_i \right) + \left( \sum_{i=l}^{r} a_i \right) \right] $$

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。