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

ayushagg31: 2017-05-25 09:28:54

Ha Ha Ha:) only one word - awesome.In the end code size is of 10 lines :)
well played /.

Last edit: 2017-05-25 09:29:16
swatantragupta: 2016-12-20 15:58:05

easy..AC in one go..nice concept

atulshanbhag: 2016-09-27 08:11:08

Can't submit! Submit goes infinite loop

Bhumit: 2016-09-16 10:52:49

First in Java. :)
AC in one go.

codehacker999: 2016-09-15 14:13:51

She sure likes Pavel to give such an easy task. Good luck bro :)

Reply: yes, I also think that he'll be out of the friendzone soon :)

Last edit: 2016-09-16 21:07:59
drajingo: 2016-09-15 12:11:03

This damn problem :') Excellent framing, hats off to the setter.


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