题目描述

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

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

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

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

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

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

输入格式

第一行一个整数 $ 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}} $ 。

样例

input

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

output

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 $。