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