You are given a sequence $a$ of length $n$ and $m$ queries. Each query asks for the frequency of the mode (the most frequent element) in a given range. The queries are provided online.

Input

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

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

The following $m$ lines each contain two integers representing the query range.

This problem requires online processing. For each query, the input values must be XORed with $lastans$. For the first query, $lastans = 0$.

Output

Output $m$ lines, each containing a single integer representing the answer to the corresponding query.

Examples

Input 1

4 1
2 3 3 3
2 4

Output 1

3

Subtasks

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

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

By nzhtl1477