[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

说明

$1\leq n,m \leq 5\times 10^5$,$0 \leq a_i\leq 10^9$。 存在 $O( n^{1.48541} )$ 的算法 Source By nzhtl1477