FRNDZND  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 multiset. Multiset is a set where an element can appear multiple times. Suppose that the size of this multiset after inserting the numbers is k. Formally, k is equal to RL+1.

Then he has to generate all possible subset of the multiset 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 multiset: {1}. There are 2 possible subset of this multiset. 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 multiset: {3,3,3}. There are 8 possible subset of this multiset. 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.
hide comments
pvsmpraveen:
20180116 15:03:34
gud one! 

coderanant:
20171214 13:18:45
AC first submission


mahilewets:
20170911 08:42:52
AC second submission.


madhur4127:
20170822 15:58:04
AC in one go, super easy! 

cs_abhi2000:
20170712 11:16:35
piece of cake :) 

sagar_zhcet:
20170629 17:32:55
Hello world after you got the logic..


ayushagg31:
20170525 09:28:54
Ha Ha Ha:) only one word  awesome.In the end code size is of 10 lines :)


swatantragupta:
20161220 15:58:05
easy..AC in one go..nice concept


atulshanbhag:
20160927 08:11:08
Can't submit! Submit goes infinite loop 

Bhumit:
20160916 10:52:49
First in Java. :)

Added by:  Bertho Coder 
Date:  20160910 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 