XOR-Closed Subarray Queries

Given a non-negative integer sequence \(a_0,a_1,\dots,a_{n-1}\) of length \(n\) (with \(1\le n\le 6\times10^5\) and \(0\le a_i < 2^{30}\)), and \(q\) queries (\(1\le q\le 10^6\)). For each query, two integers \(l\) and \(r\) (with \(0\le l\le r<n\)) are given. You need to count the number of pairs of indices \(x,y\) such that:

• \(l\le x\le y\le r\);
• If we define \(S=\{a_x,a_{x+1},\dots,a_y\}\) (i.e. the set of values in the contiguous subarray), then for every \(i,j\in S\), we have \(i\oplus j\in S\). In other words, the set \(S\) is closed under the bitwise XOR operation.

Note that if \(S\) is non-empty and is closed under XOR, then it must contain 0 (since \(x\oplus x=0\) for any \(x\)). Moreover, a nonempty set \(S\) is closed under XOR if and only if it forms a linear subspace over \(\mathbb{F}_2\); that is, if \(S\) has a basis of size \(r\), then \(|S|=2^r\).

Your task for each query is to count the number of contiguous subarrays \(a_x, a_{x+1},\dots,a_y\) within the interval \([l,r]\) for which the set of distinct numbers is XOR-closed, i.e. it satisfies \[ \text{if } S = \{a_x, \dots, a_y\}, \; 0 \in S \quad \text{and} \quad |S| = 2^{\text{rank}(S)}, \] where \(\text{rank}(S)\) is the number of elements in a basis (ignoring 0) obtained by Gaussian elimination under XOR.

Tip: Although the worst-case input sizes are large, the intended solutions must avoid unnecessary high complexity approaches. In the sample cases, the constraints are small enough for a brute force solution.

inputFormat

The first line contains two integers \(n\) and \(q\), where \(n\) is the length of the sequence and \(q\) is the number of queries.

The second line contains \(n\) non-negative integers \(a_0,a_1,\dots,a_{n-1}\) (each \(0\le a_i < 2^{30}\)).

Then \(q\) lines follow. Each contains two integers \(l\) and \(r\) (\(0\le l \le r < n\)) representing a query.

outputFormat

For each query, output a single integer representing the number of contiguous subarrays (within \(a_l\) to \(a_r\)) whose set of distinct elements is closed under the bitwise XOR operation.

sample

3 2
0 1 1
0 2
1 2

3
0