rt，我重构了一份，然而和题解写的几乎一样，但是WA了这些点。
另一个帖子说减得是区间重叠长度，但我把那一部分和题解比对了一下，觉得没有毛病。不知道是哪里挂了。

//g++ g.cpp -g -o g -std=c++14 -O0 -Wall
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define LL long long
#define printf __builtin_printf
using namespace std;
const int maxn=1e5+10,maxlgn=25,maxm=(1<<14)+10;//300,1<<14
int N,M,K,sqn,a[maxn],cnt[maxm],tn[maxm],st[maxm],stop=0;LL ans[maxn],p[maxn];
struct node{int id,l,r;}q[maxn];
struct nodev{int id,l,r,v;};
vector<nodev>vec[maxn];
bool cmp(const node &x,const node &y){return x.l/sqn==y.l/sqn?(x.l/sqn&1)^(x.r<y.r):x.l<y.l;}
int qd(){
	int rt=0;char c=getchar();
	while(c<'0'||c>'9')  c=getchar();
	while('0'<=c&&c<='9')  rt=(rt<<3)+(rt<<1)+c-48,c=getchar();
	return rt;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	N=qd(),M=qd(),K=qd(),sqn=N/sqrt(M+1);
	if(K>14){for(int i=1;i<=M;i++)  printf("0\n");return 0;}
//	printf("sqn=%d\n",sqn);
	for(int i=1;i<=N;i++)  a[i]=qd();
	for(int i=1;i<=M;i++)  q[i].l=qd(),q[i].r=qd(),q[i].id=i;
	sort(q+1,q+M+1,cmp);
//	for(int i=1;i<=M;i++)  printf("%d %d,%d\n",q[i].id,q[i].l,q[i].r);
	for(int i=1;i<maxm;i++){cnt[i]=cnt[i>>1]+(i&1);if(cnt[i]==K)  st[++stop]=i;}
	for(int i=1;i<=N;i++){p[i]=p[i-1]+tn[a[i]];for(int j=1;j<=stop;j++)  tn[st[j]^a[i]]++;}
	for(int i=1,tl=1,tr=0;i<=M;i++){
		int id=q[i].id,l=q[i].l,r=q[i].r;
		if(l<tl)  ans[id]-=p[tl-1]-p[l-1],vec[tr].push_back((nodev){id,l,tl-1,1}),tl=l;
		if(tr<r)  ans[id]+=p[r]-p[tr],vec[tl-1].push_back((nodev){id,tr+1,r,-1}),tr=r;
		if(tl<l)  ans[id]+=p[l-1]-p[tl-1],vec[tr].push_back((nodev){id,tl,l-1,-1}),tl=l;
		if(r<tr)  ans[id]-=p[tr]-p[r],vec[tl-1].push_back((nodev){id,r+1,tr,1}),tr=r;
	}
	for(int i=0;i<maxm;i++)  tn[i]=0;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=stop;j++)  tn[st[j]^a[i]]++;
		for(int j=0;j<vec[i].size();j++){
			for(int k=vec[i][j].l;k<=vec[i][j].r;k++){
				ans[vec[i][j].id]+=vec[i][j].v*(tn[a[k]]-((!K)&&k<=i));
			}
		}
	}
	for(int i=2;i<=M;i++)  ans[q[i].id]+=ans[q[i-1].id];
	for(int i=1;i<=N;i++)  printf("%lld\n",ans[i]);
	return 0;
}