XOR Subspace Segments

Given an array of nonnegative integers (a_0,a_1,\dots,a_{n-1}) of length (n) ((1\le n\le 6\times10^5)) and (q) queries, each query provides two integers (l) and (r) ((0\le l\le r<n)). For each query, count the number of contiguous subsegments ([x,y]) with (l\le x\le y\le r) such that if (S={a_k: x\le k\le y}) then for all (i,j\in S) the condition (i\oplus j\in S) holds.

A useful observation is that the property

[ \forall i,j\in S:; i\oplus j\in S ]

forces (S) to be a subspace of (\mathbb{F}_2), that is, if we let (d) be the rank of the set (S) (computed via Gaussian elimination) then (|S|=2^d) and necessarily (0\in S). In particular, note that if (|S|=1) then we must have (S={0}); if (|S|=2) then (S) has the form ({0,x}) for some nonzero integer (x); and in general if (|S|>2) then (|S|) must be a power of two.

Your task is to count the number of subsegments (i.e. contiguous intervals) ([x,y]) within ([l,r]) for which the set ({a_x, a_{x+1},\dots,a_y}) satisfies (0\in S) and (|S|=2^{(\mbox{rank}(S))}).

Note: The formulas above are written in (\LaTeX) format.

inputFormat

The first line contains two integers \(n\) and \(q\), denoting the length of the array and the number of queries.

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

Each of the next \(q\) lines 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 subsegments \([x,y]\) within the query range \([l,r]\) that satisfy the condition.

sample

4 3
0 0 0 0
0 3
1 2
2 3

10
3
1