#include<bits/stdc++.h>
#include<cstdio>
#include<cctype>
using namespace std;
#define ll long long
#define ull unsigned long long
const int N=200005,M=1e6+5;
int n,m,q,K,bl,br;
int a[N],pos[N],fp[N];
struct node{int l,r,id;}b[M];
bool cmp(node x,node y){
	if(pos[x.r]!=pos[y.r]) return x.r<y.r;
	if(pos[x.r]&1) return x.l<y.l;
	return x.l>y.l;
}
struct A{int l,r,id,v;};vector<A>tag[N];
int cnt[1200000];
#define lc k<<1
#define rc k<<1|1
#define ls lc,l,mid
#define rs rc,mid+1,r
void ins(int k,int w,int x){
	cnt[k]++;
	if(w==0) return ;
	if(!(w&x)) ins(lc,w>>1,x);
	else ins(rc,w>>1,x);
}
int ask(int k,int w,int x){
	if(w==0) return cnt[k];
	if(w&m){
		if(w&x) return cnt[rc]+ask(lc,w>>1,x);
		return cnt[lc]+ask(rc,w>>1,x);
	}
	else{
		if(w&x) return ask(rc,w>>1,x);
		return ask(lc,w>>1,x);
	}
}
ll ans[M],tmp[M];
int c1[300000],c2[300000];
int query(int x){return c1[x>>9]+c2[x];}
void add(int x){
	for(int i=17,l,r;i>=9;i--)
		if((m>>i)&1){
			l=((x>>i)<<i);
			r=l+(1<<i);
			l>>=9,r>>=9;
			for(int j=l;j<r;j++) c1[j]++;
			x^=(1<<i);
		}
	for(int i=8,l,r;i>=0;i--)
		if((m>>i)&1){
			l=((x>>i)<<i);
			r=l+(1<<i);
			for(int j=l;j<r;j++) c2[j]++;
			x^=(1<<i);
		}
}
const int MB=1<<20;
struct FastIO{
	char ib[MB+100],*p,*q;
	char ob[MB+100],*r,stk[128];
	int tp;
	FastIO(){p=q=ib,r=ob,tp=0;}
	~FastIO(){fwrite(ob,1,r-ob,stdout);}
	char read_char(){
		if(p==q){
			p=ib,q=ib+fread(ib,1,MB,stdin);
			if(p==q)return 0;
		}
		return *p++;
	}
	template<typename T>
	void read_int(T& x){
		char c=read_char(),l=0;
		for(x=0;!isdigit(c);c=read_char())l=c;
		for(;isdigit(c);c=read_char())x=x*10-'0'+c;
		if(l=='-')x=-x;
	}
	void write_char(char c){
		if(r-ob==MB)r=ob,fwrite(ob,1,MB,stdout);
		*r++=c;
	}
	template<typename T>
	void write_int(T x){
		if(x<0)write_char('-'),x=-x;
		do stk[++tp]=x%10+'0';
		while(x/=10);
		while(tp)write_char(stk[tp--]);
	}
}IO;
int main(){
	IO.read_int(n);
	IO.read_int(m);
	K=sqrt(n);
	for(int i=1;i<=n;i++) pos[i]=(i-1)/K+1;
	for(int i=1;i<=n;i++) IO.read_int(a[i]);
	for(int i=1;i<=n;i++){
		ins(1,131072,a[i]);
		fp[i]=ask(1,131072,a[i]);
	}
	m++;
	IO.read_int(q);
	for(int i=1;i<=q;i++){
		IO.read_int(b[i].l);IO.read_int(b[i].r);
		b[i].id=i;
	}
	sort(b+1,b+q+1,cmp);
	bl=1;
	for(int i=1;i<=q;i++){
		if(bl>b[i].l) tag[br].push_back((A){b[i].l,bl-1,i,1});
		while(bl>b[i].l){bl--;ans[i]-=fp[bl];}
		if(br<b[i].r) tag[bl-1].push_back((A){br+1,b[i].r,i,-1});
		while(br<b[i].r){br++;ans[i]+=(fp[br]-1);}
		if(bl<b[i].l) tag[br].push_back((A){bl,b[i].l-1,i,-1});
		while(bl<b[i].l){ans[i]+=fp[bl];bl++;}
		if(br>b[i].r) tag[bl-1].push_back((A){b[i].r+1,br,i,1});
		while(br>b[i].r){ans[i]-=(fp[br]-1);br--;}
	}
	for(int i=1,x;i<=n;i++){
		add(a[i]);
		for(int j=0;j<tag[i].size();j++)
			for(int p=tag[i][j].l;p<=tag[i][j].r;p++)
				ans[tag[i][j].id]+=query(a[p])*tag[i][j].v;
	}
	for(int i=1;i<=q;i++) ans[i]+=ans[i-1];
	for(int i=1;i<=q;i++) tmp[b[i].id]=ans[i];
	for(int i=1;i<=q;i++){
		IO.write_int(tmp[i]);
		IO.write_char('\n');
	}
	return 0;
}