/*
 *
 * 二次离线莫队算法
 *
 * 利用前缀和的思想来构造答案
 * S1(i) 表示a(1), a(2) ... a(i-1) 中和a(i)配对的数的数量
 * S2(k, i) 表示a(1), a(2) .... a(k) 中和a(i)配对的数的数量
 * a1, a2 .... an 序列里面 [L, R]区间中配对的数对个数
 * 等于sum(S1(i) - S2(L-1, i)), i = L, L+1, .... R
 *
 *
 * 首先S1是好求的，从左到右遍历一遍a序列，累加已经扫过的位置中所有数值产生的可能与其配对的数值的计数值，没到一个新
 * 位置时候，先读取前面所有数值产生了多少个当前数值的配对计数，该数值就是S1(i), 然后将统计该新加入的数值可能产生的
 * 和其配对的数值，将这些数值的计数全部加1，由于异或之后能够配对的数值是很有限的，所以每一个位置最多会有几千次更新
 * 计数的操作，复杂度还可接受
 *
 * 但是S2(L-1, i)单独在每次[L, R]的询问里面求，复杂度比较高，没法重复利用计算结果，但是如果询问量比较大，
 * 每个[L, R] 询问都会产生大量的S2(x, i)的询问，把所有S2询问全部离线收集起来，按照双关键字x排序，
 * 堆到一起算，利用莫队思想x参数从小到大右移，重复利用前面的计算结果，就可以暴力把时间复杂度压下去，所以整个
 * 是两层莫队，先构造出所有第一层莫队询问，把其中的S1询问全部算出来，然后把S2询问再用内层莫队算一次，最后组合
 * S1和S2的结果，生成最后答案
 *
 */

#include <stdio.h>
#include <vector>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;


#define N 100005
int part_len;       // 分段长度

struct query_node {
    int l;
    int r;
    int idx;
    bool negative;
};

bool operator < (const query_node& n1, const query_node& n2) {
    int g1 = n1.l / part_len, g2 = n2.l / part_len;

    if (g1 != g2) {
        return g1 < g2;
    }
    return n1.r < n2.r;
}


int arr[N];
long long SS1[N];                   // S1序列的前缀和
long long cnt[(1 << 14) + 10];      // 配对数值的计数值
long long ret[N];                   // 询问的答案
vector<query_node> S2_query[N];     // 延后计算的询问
vector<query_node> tot_query;       // 外层莫队的询问
vector<int> mask;                   // 所有二进制位数中有k个1的数值

void build_s1(int n) {
    memset(cnt, 0, sizeof(cnt));

    for (int i = 1; i <= n; i++) {
        SS1[i] = SS1[i-1] + cnt[arr[i]];;
        for (auto mask_val : mask) {
            cnt[arr[i] ^ mask_val] += 1;
        }
    }
}

// 处理延后计算的询问
void process_s2_query(int n) {
    int l, r, idx;
    bool neg;

    memset(cnt, 0, sizeof(cnt));
    for (int ii = 1; ii <= n; ii++) {
        for (auto mask_val : mask) {
            cnt[arr[ii] ^ mask_val] += 1;
        }

        long long ans = 0;
        for (auto& q : S2_query[ii]) {
            l = q.l, r = q.r, idx = q.idx, neg = q.negative;

            ans = 0;
            for (int i = l; i <= r; i++) {
                ans += cnt[arr[i]];
            }

            if (neg) {
                ret[idx] -= ans;
            } else {
                ret[idx] += ans;
            }
        }
    }
}

int one_cnt(int val) {
    int ans = 0;
    while (val) {
        ans += 1;
        val &= (val - 1);
    }
    return ans;
}


int main(void) {
    //freopen("/Users/grh/Programming/CLionProjects/Test/data.txt", "r", stdin);

    int n, m, k, L, R;
    scanf("%d %d %d", &n, &m, &k);
    part_len = sqrt(n);

    for (int val = 0; val < (1 << 14); val++) {
        if (one_cnt(val) == k) {
            mask.push_back(val);
        }
    }

    for (int i = 1; i <= n; i++) {
        scanf("%d", arr + i);
    }

    for (int idx = 0; idx < m; idx++) {
        scanf("%d %d", &L, &R);
        tot_query.push_back({L, R, idx});
    }


    build_s1(n);

    // 外层莫队
    int l, r, idx;
    sort(tot_query.begin(), tot_query.end());
    L = 1, R = 0;     // 当前处理的询问的左右边界

    for (auto&q : tot_query) {
        l = q.l, r = q.r, idx = q.idx;

        if (L < l) {
            S2_query[R].push_back({L, l-1, idx, true});
            ret[idx] += SS1[l-1] - SS1[L-1];
            if (k == 0) {
                // 处理自己匹配自己的情况
                ret[idx] += (l-1)-L+1;
            }

            L = l;
        } else if (L > l) {
            S2_query[R].push_back({l, L-1, idx, false});
            ret[idx] -= SS1[L-1] - SS1[l-1];
            if (k == 0) {
                // 处理自己匹配自己的情况
                ret[idx] -= (L-1)-l+1;
            }

            L = l;
        }

        if (R < r) {
            S2_query[L-1].push_back({R+1, r, idx, true});
            ret[idx] += SS1[r] - SS1[R];
            R = r;
        } else if (R > r) {
            S2_query[L-1].push_back({r+1, R, idx, false});
            ret[idx] -= SS1[R] - SS1[r];
            R = r;
        }
    }

    process_s2_query(n);

    // 把增量全部加和起来生成最终答案
    int idx1, idx2;
    for (int i = 1; i < m; i++) {
        idx1 = tot_query[i-1].idx;
        idx2 = tot_query[i].idx;
        ret[idx2] += ret[idx1];
    }


    for (int i = 0; i < m; i++) {
        printf("%lld\n", ret[i]);
    }

    return 0;
}