You are given an array $A$ containing $N$ integers and $Q$ queries. Each query is denoted by two integers $L, R$. The answer to a query is $A_L + (A_L \oplus A_{L+1}) + \dots + (A_L \oplus A_{L+1} \oplus \dots \oplus A_R)$, where $\oplus$ denotes the bitwise XOR operator. 

Input format

• The first line contains two integers $N$ denoting the size of array A and  $Q$  denoting the number of queries:
• The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$ - denoting the elements of A.
• Each of the next $Q$  lines contains two integers $L, R.$

Output format

For each test query, print the answer in a separate line.

Constraints

$1 \leq N, Q \leq 2\cdot 10^5\\ \\0\leq A_i \lt 2^{30} \\ 1 \le L \le R \le N$