#6290. 「XXOI 2018」某不科学的超夯基统计

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: KingSann

题目描述

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

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

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

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

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

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

输入格式

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