#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXA = 100005;

struct Node {
    int sum;
    Node *left, *right;
    Node() : sum(0), left(nullptr), right(nullptr) {}
    Node(int sum, Node* left, Node* right) : sum(sum), left(left), right(right) {}
};

int n, q, c;
int a[MAXN];
vector<int> pos[MAXA];

Node* roots_start[MAXN];
Node* roots_end[MAXN];

// Persistent segment tree for point updates and prefix sums
Node* update(Node* node, int l, int r, int pos, int delta) {
    if (!node) node = new Node();

    Node* new_node = new Node(node->sum, node->left, node->right);

    if (l == r) {
        new_node->sum += delta;
        return new_node;
    }

    int mid = (l + r) / 2;
    if (pos <= mid) {
        new_node->left = update(node->left, l, mid, pos, delta);
    } else {
        new_node->right = update(node->right, mid+1, r, pos, delta);
    }

    new_node->sum = (new_node->left ? new_node->left->sum : 0) +
                    (new_node->right ? new_node->right->sum : 0);
    return new_node;
}

int query(Node* node, int l, int r, int ql, int qr) {
    if (!node) return 0;
    if (ql <= l && r <= qr) {
        return node->sum;
    }
    int mid = (l + r) / 2;
    int res = 0;
    if (ql <= mid) res += query(node->left, l, mid, ql, qr);
    if (qr > mid) res += query(node->right, mid+1, r, ql, qr);
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q >> c;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] < MAXA) {
            pos[a[i]].push_back(i);
        }
    }

    // Generate events as difference array updates
    struct Event {
        int l, type, pos; // pos = rmin for add, or rmax+1 for subtract
    };
    vector<Event> events_start, events_end;

    for (int x = 1; x < MAXA; x++) {
        int f = pos[x].size();
        if (f < x) continue;

        vector<int> p;
        p.push_back(0);
        for (int idx : pos[x]) p.push_back(idx);
        p.push_back(n + 1);

        for (int k = 1; k + x - 1 <= f; k++) {
            int lmin = p[k - 1] + 1;
            int lmax = p[k];
            int rmin = p[k + x - 1];
            int rmax = p[k + x] - 1;

            if (lmin > lmax || rmin > rmax) continue;
            if (lmin < 1 || lmax > n || rmin < 1 || rmax > n) continue;

            // Add to start tree: at rmin +1, at rmax+1 -1
            events_start.push_back({lmin, +1, rmin});
            events_start.push_back({lmin, -1, rmax + 1});

            // Add to end tree
            if (lmax + 1 <= n) {
                events_end.push_back({lmax + 1, +1, rmin});
                events_end.push_back({lmax + 1, -1, rmax + 1});
            }
        }
    }

    // Sort events by l
    sort(events_start.begin(), events_start.end(), [](const Event& a, const Event& b) {
        return a.l < b.l;
    });
    sort(events_end.begin(), events_end.end(), [](const Event& a, const Event& b) {
        return a.l < b.l;
    });

    // Build persistent trees
    roots_start[0] = nullptr;
    roots_end[0] = nullptr;

    int ptr_start = 0, ptr_end = 0;

    for (int l = 1; l <= n; l++) {
        roots_start[l] = roots_start[l-1];
        roots_end[l] = roots_end[l-1];

        // Add all start events at this l
        while (ptr_start < events_start.size() && events_start[ptr_start].l == l) {
            auto& ev = events_start[ptr_start];
            roots_start[l] = update(roots_start[l], 1, n+1, ev.pos, ev.type);
            ptr_start++;
        }

        // Add all end events at this l
        while (ptr_end < events_end.size() && events_end[ptr_end].l == l) {
            auto& ev = events_end[ptr_end];
            roots_end[l] = update(roots_end[l], 1, n+1, ev.pos, ev.type);
            ptr_end++;
        }
    }

    // Answer queries online
    int last_ans = 0;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        if (c == 1) {
            l ^= last_ans;
            r ^= last_ans;
        }

        // Query: sum of all updates with position <= r
        // That's query(1, r) in the segment tree
        int cnt_start = query(roots_start[l], 1, n+1, 1, r);
        int cnt_end = query(roots_end[l], 1, n+1, 1, r);
        int ans = cnt_start - cnt_end;

        cout << ans << '\n';
        last_ans = ans;
    }

    return 0;
}
