Given an array $A$ of $n$ positive integers, there are $q$ queries. Each query consists of two integers $x, y$, where:
- $l = (x + \text{lastans}) \mod n + 1$
- $r = (y + \text{lastans}) \mod n + 1$.
Here, $\text{lastans}$ is the result of the previous query, and initially, we set $\text{lastans} = 0$. If $l > r$, swap the values of $l$ and $r$. Your task is to find a pair of numbers $(i, j)$ such that $l \le i \le j \le r$ and $a_i \oplus a_{i + 1} \oplus ... \oplus a_j$ is maximized.
The answer to each query is $a_i \oplus a_{i + 1} \oplus ... \oplus a_j$.
### Input
- The first line contains two integers $n, q$.
- The second line contains $n$ integers $A_i$.
- The next $q$ lines each contain two integers $x, y$, the parameters for a query.
### Output
- For each query, print an integer representing the result.
### Constraints
- $1 \le n, q \le 2 \times 10^4$.
- $1 \le x, y, A_i \le 10^9$.
### Example
Input:
```
5 3 0
8 6 2 4 5
0 4
0 2
2 4
```
Output:
```
14
6
14
```
