#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 9,SqrtN = 359,M = 1e5 + 9,V = 1 << 14;
int n,m,k;
int a[N];
struct block{
	int l,r;
} b[SqrtN];
int block_len,block_cnt;
int belong[N];
void build_block(){
	block_len = 300;block_cnt = (n + block_len - 1) / block_len;
	for(int i = 1;i <= block_cnt;i++){
		b[i].l = b[i - 1].r + 1;
		b[i].r = b[i].l + block_len - 1;
	}
	b[block_cnt].r = n;
	for(int i = 1;i <= block_cnt;i++)
		for(int j = b[i].l;j <= b[i].r;j++)
			belong[j] = i;
}
struct Query{
	int l,r;
	int id;
} q[M];
bool cmp(Query q1,Query q2){
	return (belong[q1.l] ^ belong[q2.l]) ? belong[q1.l] < belong[q2.l] : q1.r < q2.r;
}
struct Query_node{
	int l,r;//l,r这段区间对前缀产生贡献
	int ans;
};
struct Query2{
	vector<Query_node> vec;
	int pos;
	int get(){
		return vec[pos++].ans;
	}
} q2[N];
void add_query(int l,int r,int pre){
	q2[pre].vec.push_back((Query_node){l,r,0});
}
int lowbit(int x){
	return x & (-x);
}
int popcount(int x){
	int ret = 0;
	while(x){
		ret++;
		x -= lowbit(x);
	}
	return ret;
}
int valid[V],top;
int bucket[V];
int s[N];
void solve(){
	//预处理所有合法的数
	for(int i = 0;i < V;i++)
		if(popcount(i) == k)
			valid[++top] = i;

	//扫描线 
	for(int i = 1;i <= n;i++){
		s[i] = bucket[a[i]];
		for(int j = 1;j <= top;j++)
			bucket[a[i] ^ valid[j]]++;
		for(int j = 0;j < (int)q2[i].vec.size();j++)
			for(int i2 = q2[i].vec[j].l;i2 <= q2[i].vec[j].r;i2++)
				q2[i].vec[j].ans += bucket[a[i2]] - (int)(i2 <= i && k == 0);
	}
}
int ans[M];
signed main(){
	//ios::sync_with_stdio(false);
	//cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	build_block();
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	for(int i = 1;i <= m;i++){
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1,q + m + 1,cmp);
	int lres = 1,rres = 0;
	for(int i = 1;i <= m;i++){
		int L = q[i].l,R = q[i].r;
		if(lres > L)
			add_query(L,lres - 1,rres);
		if(rres < R)
			add_query(rres + 1,R,lres - 1);
		if(lres < L)
			add_query(lres,L - 1,rres);
		if(rres > R)
			add_query(R + 1,rres,lres - 1);
		lres = L;
		rres = R;
	}
	solve();
	for(int i = 1;i <= n;i++)
		s[i] += s[i - 1];
	int tmp = 0;
	lres = 1;rres = 0;
	for(int i = 1;i <= m;i++){
		int L = q[i].l,R = q[i].r;
		if(rres < R){
			tmp += s[R] - s[rres];
			tmp -= q2[lres - 1].get();
		}
		if(rres > R){
			tmp -= s[rres] - s[R];
			tmp += q2[lres - 1].get();
		}
		rres = R;
		if(lres < L){
			tmp -= q2[rres].get();
			tmp += s[L - 1] - s[lres - 1];
		}
		if(lres > L){
			tmp += q2[rres].get();
			tmp -= s[lres - 1] - s[L - 1];
		}
		lres = L;
		if(L == R)
			tmp = 0;
		ans[q[i].id] = tmp;
	}
	for(int i = 1;i <= m;i++)
		cout << ans[i] << '\n';
	return 0;
}