## FRNDZND - Friend Zoned

no tags

Pavel proposed a girl. Of course, she didn’t say yes, rather she gave him an array having N integers and asked him M queries over the array. Each query can be represented as two integers L & R.

For each query, Pavel should do the following:

1. First, he has to insert the numbers at index L, L+1, L+2,……,R of the given array into a multi-set. Multi-set is a set where an element can appear multiple times. Suppose that the size of this multi-set after inserting the numbers is k. Formally, k is equal to R-L+1.

2. Then he has to generate all possible subset of the multi-set which he constructed in step 1. Then for each subset he needs to xor the numbers of that subset. In this way, he will get 2^k values. Note that, for the empty set he will get 0.

3. Finally, he has to xor the 2^k values which he got at step 2 and say this value to his dream girl.

If Pavel can answer all the queries correctly then she will reconsider his proposal. Can you help him to answer the queries?

### Input

The first line of input contains two integers N and Q. The next line contains N integers, the numbers in the array. Then each of the following Q lines contains 2 integers L & R.

### Output

For each query output an integer in a separate line, the answer for that query. Queries should be answered in the order given in the input.

### Constraints

`1 ≤ N ≤ 1000001 ≤ Q ≤ 1000000 ≤ Value of a number in the array ≤ 10000000001 ≤ L ≤ N1 ≤ R ≤ NL ≤ R`

### Example

`Input:4 21 3 3 31 12 4`
`Output:10`
`Explanation: In the first query, there will be only 1 element in the multi-set: {1}. There are 2 possible subset of this multi-set. They are: { }, {1}. If we xor the numbers of each subset we get 0 & 1 respectively. Xor of theses two values is equal to 1.In the second query, there are 3 elements in the multi-set: {3,3,3}. There are 8 possible subset of this multi-set. They are: { }, {3}, {3}, {3}, {3,3}, {3,3}, {3,3}, {3,3,3}. By applying xor operation on the numbers of each subset we get 0, 3, 3, 3, 0, 0, 0, 3 respectively. Xor of these values is equal to 0.`