Sub-subsequence - MarisaOJ: Marisa Online Judge

Sub-subsequence

Time limit: 2000 ms
Memory limit: 512 MB
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 8 6 2 4 5 0 4 0 2 2 4 ``` Output: ``` 14 6 14 ```