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