#include <bits/stdc++.h>
	
using namespace std;

int read() {
	char c = getchar();
	int v = 0;
	
	while (c < '0') {
		c = getchar();
	}
	
	while (c >= '0') {
		v = v * 10 + c - 48;
		c = getchar();
	}
	
	return v;
}

const int N = 1e5 + 3, V = 1e6 + 3;

int n, m, k;
int num[2][V], a[N], bl[N];
long long now, ans[N];

struct node {
	int l, r, id;
} q[N];

int cmp(node x, node y) {
	if (bl[x.l] ^ bl[y.l]) return bl[x.l] < bl[y.l];
	return bl[x.l] & 1 ? x.r < y.r : x.r > y.r;
}

signed main() {		
	n = read(), m = read();
	k = n / sqrt(m);
	for (int i = 1; i <= n; i++) {
		a[i] = a[i - 1] ^ (read() - 1);
		bl[i] = (i - 1) / k + 1;
	}
	
	for (int i = 1; i <= m; i++) {
		q[i].l = read() - 1, q[i].r = read();
		q[i].id = i;
	}
	
	sort(q + 1, q + 1 + m, cmp);
	
	int l = 1, r = 0;
	
	for (int i = 1; i <= m; i++) {
		int ql = q[i].l, qr = q[i].r;
		while (l < ql) now -= --num[l & 1][a[l]], l++;
		while (l > ql) l--, now += num[l & 1][a[l]]++;;
		while (r < qr) r++, now += num[r & 1][a[r]]++;
		while (r > qr) now -= --num[r & 1][a[r]], r--;
		ans[q[i].id] = 1ll * (qr - ql + 1) * (qr - ql) / 2 - now;
	}
	
	for (int i = 1; i <= m; i++) {
		printf("%lld\n", ans[i]);
	}
	
	return 0;
}