XOR of Subarray Distinct Counts

Given a sequence \(a_1,a_2,\dots,a_n\) and \(m\) queries, each query consists of two integers \(l\) and \(r\). For each query, consider every subarray \((L,R)\) such that \(l \le L \le R \le r\). The weight of a subarray \((L,R)\) is defined as \(|\{a_i: L \le i \le R\}|\), i.e. the number of distinct elements in that subarray.

Your task is to compute the bitwise XOR of the weights of all subarrays within the given range. Formally, for each query, you need to calculate:

\[ \bigoplus_{L=l}^{r} \bigoplus_{R=L}^{r} \left|\{a_i: L \le i \le R\}\right|, \]

Note: The problem constraints in the provided test cases are relatively small, so a brute force solution that precomputes the distinct counts for every subarray is sufficient.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n, m \le 10^5)\), representing the number of elements in the sequence and the number of queries respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the sequence.

The following \(m\) lines each contain two integers \(l\) and \(r\) \((1 \le l \le r \le n)\) representing a query.

outputFormat

For each query, output a single integer on a new line — the bitwise XOR of the weights of all subarrays \((L,R)\) such that \(l \le L \le R \le r\).

sample

3 1
1 2 1
1 3

3