XOR of Distinct Counts in Subarrays

Given a sequence (a_1,\dots,a_n) and (m) queries, each query provides two integers (l) and (r). For each query, consider all pairs ((L, R)) satisfying (l \le L \le R \le r). The weight of a pair ((L,R)) is defined as (\left|{ a_i \mid L \le i \le R }\right|), i.e. the number of distinct elements in the subarray (a_L, a_{L+1},\dots,a_R). Compute the bitwise XOR of these weights over every valid pair in the query range.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the size of the sequence and the number of queries.

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

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

outputFormat

For each query, output a single integer — the XOR of the weights of all subarrays \((L,R)\) satisfying \(l\le L\le R\le r\).

sample

3 2
1 2 1
1 3
2 3

3
2