题目描述
众所周知,基因与人类密切相关,那么本题来谈谈关于夯基的那部分。
夯基,是大力出的奇基,存在着一些神秘的性质。
如果有两个基因的编号相同,那么这两个基因属于同种基因。
假设有一个连续的基因序列,对于任意一个连续的子基因片段,我们称它的夯基为出现次数最多,且编号最小的基因。
御坂在一次任务期间偶然得到了一个珍贵的基因序列,木山知道后便问了她几个问题,每次诸如询问一个子基因片段的夯基是那个。
御坂当然答不出来啦,于是来寻求夯水手,也就是你的帮助。
输入格式
第一行一个整数 T,表示测试点编号。
第二行两个整数 n,m,分别表示基因序列长度和询问次数。
第三行有 n 个整数,表示基因序列的每一个基因的编号。
接下来 m 行,每行诸如两个整数 l 和 r,表示询问基因序列的 [l,r] 子基因片段的夯基是哪个。
输出格式
首先对于每一个询问将答案输出到一行,用空格分开(最后一个询问之后不输出空格)
由于御坂不想看这么多的数据,所以需要你告诉她这个值:将所有的询问答案按照询问顺序进行排序,可以得到一个序列(先询问的在前),然后你需要输出 (对于所有的连续子序列[l,r],l≤r) ((bitandi=lrai)+(∑i=lrai))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≤y≤r,要么 x<l≤r≤y 。
特殊性质 3:对于任意两个询问区间 [l,r] 和 [x,y],要么不相交,要么 l≤x≤y≤r,要么 x≤l≤r≤y 。
对于所有数据,保证 1≤n,m≤5×105,1≤ai≤n,1≤l≤r≤n。