[Ynoi2019模拟赛]Yuno loves sqrt technology III

题目描述

![](https://cdn.luogu.com.cn/upload/pic/44006.png) 给你一个长为n的序列a,m次询问,每次查询一个区间的众数的出现次数,强制在线

输入输出格式

输入格式


第一行两个数n,m 第二行n个数表示这个序列 之后m行,每行两个数表示查询的区间 本题强制在线,每次查询输入的数要xor上lastans,第一次询问默认lastans=0

输出格式


输出m行,每行一个数表示这次询问的答案

输入输出样例

输入样例 #1

4 1
2 3 3 3
2 4

输出样例 #1

3

说明

n,m <= 500000,0 <= ai <= 1000000000 如果有人这题得到了低于nsqrtn复杂度的做法,请发表论文,让我们康康哦~ 听说可能已经有了低于n^1.5的算法 Source By nzhtl1477