F

#include <algorithm>
#include <iostream>
#include <array>
#include <vector>
#include <numeric>
#include <random>
#include <chrono>
#include <set>
#include <map>
#include <queue>

using namespace std;

const long long INF = 1e9 + 7;
const int MAXN = 1e5 + 10;
const int N = 1e5 + 10;
const int MAX_VALUE = 1e6 + 1;
const int B = 1000;

struct Query {
    int l, r, i;

    Query() = default;

    Query(int l_, int r_, int i_) : l(l_), r(r_), i(i_) {};
};

bool comp(const Query& lhs, const Query& rhs) {
    return lhs.l / B < rhs.l / B || lhs.l / B == rhs.l / B && lhs.r < rhs.r;
}

int k;
int mp[MAX_VALUE];
int ans = 0;

inline void add(int x) {
    ++mp[x];
    if (mp[x] == k + 1) {
        --ans;
    } else if (mp[x] == k) {
        ++ans;
    }
}

inline void pop(int x) {
    --mp[x];
    if (mp[x] == k - 1) {
        --ans;
    } else if (mp[x] == k) {
        ++ans;
    }
}

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

    int n, m, q;
    cin >> n >> m >> q >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    if (k == 0) {
        ans = m;
    }
    vector<Query> ask;
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        ask.emplace_back(l - 1, r - 1, i);
    }
    sort(ask.begin(), ask.end(), comp);
    int left = 0, right = -1;
    vector<int> answer(q);
    for (int i = 0; i < q; ++i) {
        const auto [l, r, pos] = ask[i];
        while (right < r) {
            add(a[++right]);
        }
        while (left > l) {
            add(a[--left]);
        }
        while (right > r) {
            pop(a[right--]);
        }
        while (left < l) {
            pop(a[left++]);
        }
        answer[pos] = ans;
    }

    for (const auto i : answer) {
        cout << i << '\n';
    }
}