XOR Sequence Queries

Given a sequence \(\{a\}\) of length \(K\), an infinite sequence \(\{x\}\) is defined as follows:

\[ x_n = \begin{cases} a_n, & 1 \le n \le K, \\ \bigoplus_{i=n-K}^{n-1} x_i, & n > K, \end{cases} \]

Here, \(\bigoplus\) denotes the bitwise XOR operation.

You are given \(Q\) queries. Each query consists of two positive integers \(l\) and \(r\); for each query, compute:

\[ \bigoplus_{i=l}^{r} x_i \]

Note: For \(K \ge 2\), it can be shown that the sequence \(\{x\}\) is periodic with period \(K+1\). In the special case \(K=1\), the sequence is constant.

inputFormat

The first line contains two integers \(K\) and \(Q\) separated by a space.

The second line contains \(K\) integers \(a_1, a_2, \dots, a_K\) which are the elements of the sequence \(\{a\}\).

Each of the next \(Q\) lines contains two integers \(l\) and \(r\) representing a query.

\(1 \leq l \leq r\).

outputFormat

For each query, output a single integer which is the value of \(\bigoplus_{i=l}^{r} x_i\) on a new line.

sample

3 2
1 2 3
1 4
2 5

0
0