当挪动一次莫队指针的复杂度为 \(O(k)\) 时，普通莫队的复杂度为 \(O(n\sqrt(n)k)\)
设 \(f(x,l,r)\) 为 \(x\) 对 \([l,r]\) 区间的贡献，那么当：

• \(f(x,l,r)\) 只与 \([l,r]\) 内元素有关
• \(f(x,l,r)=f(x,1,r)-f(x,1,l-1)\)

时，可以用莫队二次离线优化到 \(O(nk+n\sqrt(n))\)

以目前的 \(r\) 指针小于当前询问的右端点（设当前询问的左右端点分别是 \(L,R\))，指针向右移动为例，对答案的贡献就是

\[\sum_{x=r+1}^R f(x,L,x-1)=\sum_{x=r+1}^R f(x,1,x-1)-\sum_{x=r+1}^R f(x,1,L-1) \]

这个 \(f(x,1,x-1)\) 可以 \(O(nk)\) 预处理出来，而后面那一项用 \((L-1,r+1,R,i,k)\) 表示，进行第二次离线。其中 \(i\) 是询问的编号，\(k\) 是正一或负一的系数
然后莫队结束后对 \(L-1\) 从小到大处理

移动其他指针类似，会产生一个 \(f(x,1,x)\)，同样预处理即可，但一般来说一个数不会对自己产生贡献，所以只预处理一个就好了
当在第 \(i\) 个询问移动莫队指针时，产生的贡献会被算到 \([i,m]\) 中的所有询问里，所以这样求得的答案实际上是一个差分后的答案

模板题：https://www.luogu.com.cn/problem/P4887
预处理时，由于 \(a\operatorname{xor} b=c\Rightarrow a=b\operatorname{xor} c\)，记录下所有 \(\operatorname{popcount}\) 为 \(k\) 的数，开桶即可

#define N 100006
#define B 316
int n,m,k;
struct Ask{
	int l,r,id;
};
Ask ask[N];
struct Node{
	int L,R,i,k;
};
std::vector<Node>change[N];
int a[N],belong[N];
int fxx[N];
long long ans[N];
int main(){
	n=read();m=read();k=read();
	if(k>14){
		for(int i=1;i<=m;i++) write("0\n");
		return RET;
	}
	for(int i=1;i<=n;i++) a[i]=read(),belong[i]=(i-1)/B+1;
	static int num[16384],t[16384];
	for(int i=0;i<16384;i++)if(__builtin_popcount(i)==k) num[++num[0]]=i;
	for(int i=1;i<=n;i++){
		fxx[i]=t[a[i]];
		for(int j=1;j<=num[0];j++) t[a[i]^num[j]]++;
	}
	for(int i=1;i<=m;i++) ask[i].l=read(),ask[i].r=read(),ask[i].id=i;
	std::sort(ask+1,ask+1+m,[](const Ask &a,const Ask &b){return belong[a.l]==belong[b.l]?a.r<b.r:a.l<b.l;});
	for(int l=1,r=0,i=1;i<=m;i++){
		if(r<ask[i].r) change[l-1].push_back({r+1,ask[i].r,i,-1});
		while(r<ask[i].r) ans[ask[i].id]+=fxx[++r];
		if(l>ask[i].l) change[r].push_back({ask[i].l,l-1,i,1});
		while(l>ask[i].l) ans[ask[i].id]-=fxx[--l];
		if(r>ask[i].r) change[l-1].push_back({ask[i].r+1,r,i,1});
		while(r>ask[i].r) ans[ask[i].id]-=fxx[r--];
		if(l<ask[i].l) change[r].push_back({l,ask[i].l-1,i,-1});
		while(l<ask[i].l) ans[ask[i].id]+=fxx[l++];
	}
	std::memset(t,0,sizeof t);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=num[0];j++) t[a[i]^num[j]]++;
		for(const Node &x:change[i]){
			for(int j=x.L;j<=x.R;j++){
				if(j<=i&&!k) ans[ask[x.i].id]+=x.k*(t[a[j]]-1);
				else ans[ask[x.i].id]+=x.k*t[a[j]];
			}
		}
	}
	for(int i=1;i<=m;i++) ans[ask[i].id]+=ans[ask[i-1].id];
	for(int i=1;i<=n;i++) writeEN(ans[i]);
	return RET;
}