Background

Problem Description

You are given a sequence $a$ of length $n$ and $m$ queries. For each query, you need to output the number of occurrences of the mode in a given interval, and the queries are forced to be online.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers representing the sequence.

Then follow $m$ lines, each containing two numbers representing the query interval.

This problem is forced to be online: in each query, the input numbers should be $\operatorname{xor}$ with $lastans$. For the first query, $lastans = 0$ by default.

Output Format

Output $m$ lines, each line contains one integer representing the answer to the query.

4 1
2 3 3 3
2 4

3

Hint

$1\leq n, m, a_i \leq 5\times 10^5$。

There exists an $O( n^{1.48541} )$ algorithm.

Source By nzhtl1477.

Translated by ChatGPT 5