// Problem: P7906 [Ynoi2005] rpxleqxq
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7906
// Memory Limit: 128 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define poly vector<ll>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < ll,ll >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define N 200005
using namespace std;
ll tag[N],all[300005],From[N];
struct qry
{
	ll l,r,id;
}q[1000005];
ll pre[N];
ll a[N];
ll ans[1000005],Ans[1000005];
ll lim;
ll n;
ll m;
const ll B=300;
struct node
{
	int tp,id,l,r;
	node(int x=0,int y=0,int a=0,int b=0)
	{
		tp=x,id=y,l=a,r=b;
	}
};
vector<node>G[N];
inline void add(ll x)
{
	for (ll i=0;i<(1<<10);i++)
		if (((x>>9)^i)<(lim>>9))
		{
			tag[i]++;
		}
	ll hi=(lim>>9)^(x>>9);
	for (ll i=0;i<(1<<9);i++)
		if ((x^(hi<<9)^i)<=lim)
		{
			all[(hi<<9)^i]++;
		}
}
inline void ers(ll x)
{
	for (ll i=0;i<(1<<10);i++)
		if (((x>>9)^i)<(lim>>9))
		{
			tag[i]--;
		}
	ll hi=(lim>>9)^(x>>9);
	for (ll i=0;i<(1<<9);i++)
		if ((x^(hi<<9)^i)<=lim)
		{
			all[(hi<<9)^i]--;
		}
}
inline ll qrry(ll x)
{
	// cout<<"?"<<x<<" "<<tag[x>>9]<<endl;
	return tag[x>>9]+all[x];
}
void BellaKira()
{
	cin>>n>>lim;
	for (ll i=1;i<=n;i++)
	{
		cin>>a[i];
		From[i]=(i-1)/B+1;
	}
	cin>>m;
	for (ll i=1;i<=m;i++)
	{
		cin>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	sort(q+1,q+m+1,[&](qry x,qry y)
	{
		return (From[x.l]^From[y.l])?From[x.l]<From[y.l]:((From[x.l]&1)?x.r<y.r:x.r>y.r);
	});
	for (ll i=1;i<=n;i++)
		pre[i]=pre[i-1]+qrry(a[i]),add(a[i]);
	for (ll i=1;i<=n;i++)
		ers(a[i]);
	ll l=1,r=0;
	for (ll i=1;i<=m;i++)
	{
		if (r<q[i].r)
		{
			G[l-1].push_back(node(-1,i,r+1,q[i].r));
			ans[i]+=pre[q[i].r]-pre[r];
			r=q[i].r;
		}
		// cout<<l<<","<<r<<endl;
		if (l>q[i].l)
		{
			G[r].push_back(node(1,i,q[i].l,l-1));
			ans[i]-=(pre[l-1]+l-1)-(pre[q[i].l-1]+q[i].l-1);
			l=q[i].l;
		}
		// cout<<l<<","<<r<<endl;
		if (r>q[i].r)
		{
			G[l-1].push_back(node(1,i,q[i].r+1,r));
			ans[i]-=pre[r]-pre[q[i].r];
			r=q[i].r;
		}
		// cout<<l<<","<<r<<endl;
		if (l<q[i].l)
		{
			G[r].push_back(node(-1,i,l,q[i].l-1));
			ans[i]+=(pre[q[i].l-1]+q[i].l-1)-(pre[l-1]+l-1);
			l=q[i].l;
		}
		// cout<<l<<","<<r<<endl;
		// cout<<q[i].l<<" "<<q[i].r<<'\n';
	}
	for (ll i=1;i<=n;i++)
	{
		add(a[i]);
		for (auto u:G[i])
		{
			ll tt=0;
			for (ll j=u.l;j<=u.r;j++)
				tt+=1ll*u.tp*qrry(a[j]);
			ans[u.id]+=tt;
		}
	}
	for (ll i=1;i<=m;i++) ans[i]+=ans[i-1];
	for (ll i=1;i<=m;i++)
		Ans[q[i].id]=ans[i];
	for (ll i=1;i<=m;i++) cout<<Ans[i]<<'\n';
			
			
}
signed main()
{
	IOS;
	cin.tie(0);
	ll T=1;
	while (T--)
	{
		BellaKira();
	}
}