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 ≤ 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.


hide comments
vineetjai: 2020-09-10 06:30:35

Nice one.

rising_stark: 2020-04-28 04:41:46

I didn't understand. Why was the word "Of Course" added in the description.

ankkt16: 2019-11-20 19:09:43

I would like to meet a girl who asks such questions

prateek_imkp1: 2018-06-19 15:17:00

Nice one . I guess she likes Pavel !

pvsmpraveen: 2018-01-16 15:03:34

gud one!

coderanant: 2017-12-14 13:18:45

AC first submission
What a nice tricky one
Hats off to the setter

Last edit: 2017-12-14 13:19:25
mahilewets: 2017-09-11 08:42:52

AC second submission.
WA first submission because I forgot there is 1-indexing in that task.

madhur4127: 2017-08-22 15:58:04

AC in one go, super easy!

cs_abhi2000: 2017-07-12 11:16:35

piece of cake :)

sagar_zhcet: 2017-06-29 17:32:55

Hello world after you got the logic..
loved solving it..


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