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$