#include <algorithm> #include <iostream> #include <utility> #include <vector> using namespace std; using i64 = long long; template <class T> struct BIT { int len; vector<T> tree; BIT(int n) : len(n) , tree(n + 1) { } BIT(const vector<T>& arr) : len(arr.size()) , tree(arr.size() + 1) { for (int i = 1; i <= len; ++i) { int j = i + (i & -i); tree[i] += arr[i - 1]; if (j <= len) tree[j] += tree[i]; } } void update(int pos, T val) { for (; pos <= len; pos += pos & -pos) tree[pos] += val; } void update(int l, int r, T val) { update(l, val); update(r + 1, -val); } T query(int pos) const { T res = 0; for (; pos > 0; pos -= pos & -pos) res += tree[pos]; return res; } T query(int l, int r) const { return l > r ? T() : (l == 1 ? query(r) : query(r) - query(l - 1)); } }; 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 lhs.second - lhs.first < rhs.second - rhs.first; }); int i = 0; BIT<int> cnts(n); vector<int> ans(n + 1); for (int d = 1; d <= n; ++d) { for (; i < m && segs[i].second - segs[i].first + 1 <= d; ++i) cnts.update(segs[i].first, segs[i].second, 1); ans[d] = m - i; for (int j = 0; j <= n; j += d) ans[d] += cnts.query(j); } while (q-- > 0) { int d; cin >> d; cout << ans[d] << '\n'; } return 0; } // inverse: // len > d are covered // len <= d are useful