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
