import sys

def count_trains_in_windows(n, x, starts, events):
    # events: list of (time, train)
    events.sort()
    qs = [(s, idx) for idx, s in enumerate(starts)]
    qs.sort()

    cnt = [0] * n
    distinct = 0
    ans = [0] * len(starts)

    l = 0
    r = 0
    m = len(events)

    for s, idx in qs:
        left = s
        right = s + x  # 左闭右开 [s, s+x)

        # 移除 time < left 的事件
        while l < m and events[l][0] < left:
            t, train = events[l]
            cnt[train] -= 1
            if cnt[train] == 0:
                distinct -= 1
            l += 1

        # 加入 time < right 的事件
        while r < m and events[r][0] < right:
            t, train = events[r]
            if cnt[train] == 0:
                distinct += 1
            cnt[train] += 1
            r += 1

        ans[idx] = distinct

    return ans

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    p = 0
    n, x, k = data[p], data[p+1], data[p+2]
    p += 3

    starts = data[p:p+k]
    p += k

    m = data[p]
    p += 1

    events = []
    for _ in range(m):
        i = data[p]
        j = data[p+1]
        p += 2
        events.append((j, i))  # (time, train)

    res = count_trains_in_windows(n, x, starts, events)
    sys.stdout.write(" ".join(map(str, res)))  # 一行输出，用空格隔开

if __name__ == "__main__":
    main()

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

// 核心功能：统计每个窗口内出现过的火车数量
static vector<int> countTrainsInWindows(
    int n, int x,
    const vector<int>& starts,
    vector<pair<int,int>>& events // (time, train)
) {
    sort(events.begin(), events.end()); // 按时间升序

    int k = (int)starts.size();
    vector<pair<int,int>> qs; // (S, idx)
    qs.reserve(k);
    for (int i = 0; i < k; i++) qs.push_back({starts[i], i});
    sort(qs.begin(), qs.end());

    vector<int> cnt(n, 0); // 每辆火车在窗口内出现次数
    int distinct = 0;      // 当前窗口内出现过的火车数
    vector<int> ans(k, 0);

    int l = 0, r = 0;
    int m = (int)events.size();

    for (auto &q : qs) {
        int s = q.first;
        int idx = q.second;
        int left = s;
        int right = s + x; // 左闭右开 [S, S+X)

        // 移除 time < left 的事件
        while (l < m && events[l].first < left) {
            int train = events[l].second;
            cnt[train]--;
            if (cnt[train] == 0) distinct--;
            l++;
        }

        // 加入 time < right 的事件
        while (r < m && events[r].first < right) {
            int train = events[r].second;
            if (cnt[train] == 0) distinct++;
            cnt[train]++;
            r++;
        }

        ans[idx] = distinct;
    }

    return ans;
}

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

    int N, X, K;
    cin >> N >> X >> K;

    vector<int> starts(K);
    for (int i = 0; i < K; i++) cin >> starts[i];

    int M;
    cin >> M;

    vector<pair<int,int>> events;
    events.reserve(M);
    for (int i = 0; i < M; i++) {
        int I, J;
        cin >> I >> J;
        events.push_back({J, I}); // (time, train)
    }

    vector<int> ans = countTrainsInWindows(N, X, starts, events);

    // 一行输出，用空格隔开
    for (int i = 0; i < K; i++) {
        if (i) cout << " ";
        cout << ans[i];
    }
    return 0;
}

import java.util.*;

public class Main {

    // 事件：上车时间 + 火车编号
    static class Event {
        int time, train;
        Event(int time, int train) {
            this.time = time;
            this.train = train;
        }
    }

    // 查询：起点S + 原下标
    static class Query {
        int s, idx;
        Query(int s, int idx) {
            this.s = s;
            this.idx = idx;
        }
    }

    // 核心功能：统计每个窗口内出现过的火车数量
    static int[] countTrainsInWindows(int n, int x, int[] starts, Event[] events) {
        Arrays.sort(events, Comparator.comparingInt(a -> a.time));

        int k = starts.length;
        Query[] qs = new Query[k];
        for (int i = 0; i < k; i++) qs[i] = new Query(starts[i], i);
        Arrays.sort(qs, Comparator.comparingInt(a -> a.s));

        int[] cnt = new int[n]; // 每辆火车在窗口内出现次数
        int distinct = 0;       // 当前窗口内出现过的火车数
        int[] ans = new int[k];

        int l = 0, r = 0, m = events.length;

        for (Query q : qs) {
            int left = q.s;
            int right = q.s + x; // 左闭右开 [S, S+X)

            // 移除 time < left 的事件
            while (l < m && events[l].time < left) {
                int train = events[l].train;
                cnt[train]--;
                if (cnt[train] == 0) distinct--;
                l++;
            }

            // 加入 time < right 的事件
            while (r < m && events[r].time < right) {
                int train = events[r].train;
                if (cnt[train] == 0) distinct++;
                cnt[train]++;
                r++;
            }

            ans[q.idx] = distinct;
        }

        return ans;
    }

    public static void main(String[] args) {
        // 按要求：不使用快读快写，直接用 Scanner
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int x = sc.nextInt();
        int k = sc.nextInt();

        int[] starts = new int[k];
        for (int i = 0; i < k; i++) starts[i] = sc.nextInt();

        int m = sc.nextInt();
        Event[] events = new Event[m];
        for (int i = 0; i < m; i++) {
            int train = sc.nextInt();
            int time = sc.nextInt();
            events[i] = new Event(time, train);
        }

        int[] ans = countTrainsInWindows(n, x, starts, events);

        // 一行输出，用空格隔开
        for (int i = 0; i < k; i++) {
            if (i > 0) System.out.print(" ");
            System.out.print(ans[i]);
        }

        sc.close();
    }
}