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\)