You are given an array $$a$$ of $$n$$ numbers and $$q$$ queries. In each query, $$l$$, $$r$$ find $$XOR$$ of all $$n$$ numbers except the range $$[l, r]$$.

Input format

• The first line contains two integers $$n$$ denoting the number of elements and $$q$$ denoting the number of test cases.
• The second line of each test case contains $$n$$ space-separated integers.
• The next $$q$$ lines contain two integers $$l$$ and $$r$$.

Output format

For each test case, print the answer as described in the problem statement.

Example 

Let the array $$a$$ be $$[1, 2, 3, 4]$$ and you are given a query $$(2, 3)$$, then print the $${XOR}$$ of all the array $$a$$ without the range $$[2, 3]$$.

Hence, the answer will be $$1 $${XOR}$$ 4$$. 

Constraints

$$1 \le   n  \le  10^5$$

$$1 \le   q    \le  {10^5}$$

$$1 \le  a_i  \le {10^9}$$

$$1 \le  l, r  \le  n$$