Cumulative XOR of Partial Sums

You are given a sequence (a) of length (n) and (q) queries. For each query, you are given two positive integers (l) and (r). Your task is to compute the value [ \bigoplus_{k=l}^{r} \left(\sum_{i=l}^{k} a_i\right) = (a_l) \oplus (a_l+a_{l+1}) \oplus (a_l+a_{l+1}+a_{l+2}) \oplus \dots \oplus (a_l+a_{l+1}+\dots+a_r), ] where (\oplus) denotes the bitwise XOR operation.

Note: Input indices are 1-indexed.

inputFormat

The first line contains two integers (n) and (q), representing the length of the sequence and the number of queries respectively. The second line contains (n) space-separated integers (a_1,a_2,\dots,a_n). The following (q) lines each contain two integers (l) and (r) representing a query.

outputFormat

For each query, output a single line containing the result of the XOR of the partial sums from index (l) to (r).

sample

5 3
1 2 3 4 5
1 3
2 4
1 5

4
14
1