Friend Zoned
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:
-
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.
-
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.
-
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 ≤ 100000
1 ≤ Q ≤ 100000
0 ≤ Value of a number in the array ≤ 1000000000
1 ≤ L ≤ N
1 ≤ R ≤ N
L ≤ R
Example
Input:
4 2
1 3 3 3
1 1
2 4
Output:
1
0
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.