SP28352 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: 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?

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.

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.