#include <algorithm> #include <iostream> #include <utility> #include <vector> using namespace std; using i64 = long long; struct Segtree { int len; vector<vector<int>> tree; vector<int> ptr; Segtree(int n) : len(n) , tree(n << 2) { } void insert(int idx, int val) { insert(idx, val, 1, len, 1); } int query(int l, int r, int val) { return l > r ? 0 : query(l, r, val, 1, len, 1); } private: void insert(int idx, int val, int l, int r, int pos) { tree[pos].push_back(val); if (l == r) return; int mid = (l + r) >> 1; if (idx <= mid) insert(idx, val, l, mid, pos << 1); else insert(idx, val, mid + 1, r, pos << 1 | 1); } int query(int lo, int hi, int val, int l, int r, int pos) { if (lo <= l && r <= hi) return upper_bound(tree[pos].begin(), tree[pos].end(), val) - tree[pos].begin(); int res = 0, mid = (l + r) >> 1; if (lo <= mid) res += query(lo, hi, val, l, mid, pos << 1); if (hi > mid) res += query(lo, hi, val, mid + 1, r, pos << 1 | 1); return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m, q; cin >> n >> m >> q; vector<pair<int, int>> segs(m); for (auto& seg : segs) cin >> seg.first >> seg.second; sort(segs.begin(), segs.end(), [](pair<int, int> lhs, pair<int, int> rhs) { return make_pair(lhs.second, lhs.first) < make_pair(rhs.second, rhs.first); }); Segtree right(n); for (auto seg : segs) right.insert(seg.first, seg.second); vector<int> ans(n + 1); for (int d = 1; d <= n; ++d) { ans[d] = m; for (int i = 0; i <= n; i += d) ans[d] -= right.query(i + 1, min(n, i + d - 1), i + d - 1); } while (q-- > 0) { int d; cin >> d; cout << ans[d] << '\n'; } return 0; } // inverse: // len > d are covered // len <= d are useful