A. Your Shine Your Be!
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a sequence of non-negative integers $$$a_1, a_2, \dots, a_n$$$ of length $$$n$$$.

There are $$$q$$$ queries. Each query provides an interval $$$[l, r]$$$. For each query, you need to consider the multiset $$$V$$$ formed by the elements in the interval $$$[l, r]$$$, and select a subset $$$M \subseteq V$$$ of maximum size such that all elements in $$$M$$$ have pairwise distinct values.

After that, you may choose any subset $$$T \subseteq M$$$ (including the empty set). Let $$$|M|$$$ denote the size of set $$$M$$$, and let $$$X_T$$$ denote the bitwise XOR of all elements in $$$T$$$ (the XOR of the empty set is defined as $$$0$$$). Your task is to compute the minimum possible value of $$$|M| \oplus X_T$$$.

This problem is online. The query inputs $$$l', r'$$$ are encrypted. Let the answer to the previous query be $$$lastans$$$ (initially $$$lastans = 0$$$). The actual query endpoints $$$l, r$$$ are obtained as follows:

$$$$$$l = (l' \oplus lastans) \bmod n + 1$$$$$$

$$$$$$r = (r' \oplus lastans) \bmod n + 1$$$$$$

After decryption, if $$$l \gt r$$$, you should swap $$$l$$$ and $$$r$$$.

Input

The first line contains two integers $$$n, q$$$ ($$$1 \le n, q \le 5 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$).

The following $$$q$$$ lines each contain two integers $$$l', r'$$$ ($$$0 \le l', r' \le 2 \cdot 10^9$$$), representing the encrypted query interval endpoints.

Output

For each query, output one integer on a separate line representing the answer.

Example
Input
6 3
4 4 6 6 0 0
6 6
2 4
6 3
Output
1
2
1
Note

Initially, $$$lastans = 0$$$.

  • For the first query, after decryption we get $$$l = 1, r = 1$$$. The set of elements in the interval is $$$S = \{4\}$$$, and $$$|S| = 1$$$. Choose the empty set $$$\varnothing$$$ (whose XOR sum is $$$0$$$), then the answer is $$$1 \oplus 0 = 1$$$. Update $$$lastans = 1$$$.
  • For the second query, after decryption we get $$$l = 4, r = 6$$$. The set of elements in the interval is $$$S = \{0, 6\}$$$, and $$$|S| = 2$$$. Choose the empty set $$$\varnothing$$$ (whose XOR sum is $$$0$$$), then the answer is $$$2 \oplus 0 = 2$$$. Update $$$lastans = 2$$$.
  • For the third query, after decryption we get $$$l = 5, r = 2$$$, so we swap the endpoints and obtain $$$[2, 5]$$$. The set of elements in the interval is $$$S = \{0, 4, 6\}$$$, and $$$|S| = 3$$$. Choose the subset $$$\{4, 6\}$$$ (whose XOR sum is $$$2$$$), then the answer is $$$3 \oplus 2 = 1$$$. Update $$$lastans = 1$$$.

The input and output size of this problem is large, so it is recommended to use fast I/O methods. For C++ contestants, it is recommended to use scanf/printf, or disable synchronization when using cin/cout:

std::ios::sync_with_stdio(false);

std::cin.tie(nullptr);